О БИЛИНЕЙНОЙ СЛОЖНОСТИ УМНОЖЕНИЯ МАТРИЦ РАЗМЕРОВ m × 2 И 2 × 2

В данной работе исследуется сложность умножения матриц. Ф. Штрассен в 1969 году [1] построил алгоритм для умножения двух матриц порядка n с числом арифметических операций O ( n log2 7 ) , что асимптотически лучше, чем сложность порядка n 3 стандартного алгоритма умножения матриц «строка на столбец». В последующие годы проводились активные исследования минимальной сложности различных алгебраических операций. Результаты исследований в этой области хорошо отражены в книге [2]. Ситуация в задаче об умножении матриц оказалась достаточно тяжелой. К концу 1980-х годов усилиями многих математиков сложность умно- жения матриц удалось понизить до O ( n 2.38) [3], но с тех пор существенных продвижений в этой задаче нет. Для того, чтобы лучше понять проблемы, возникающие при поиске быстрых алгоритмов умножения матриц, эта задача исследуется в разных направлениях. Одним из таких направлений является исследование мини- мальной сложности умножения матриц малых размеров. Эти исследова- ния имеют самостоятельный интерес, а также связаны с тем, что быстрые алгоритмы для умножения матриц малых размеров могут рекурсивно ис- пользоваться для умножения матриц больших размеров. В частности, алгоритм Штрассена основан на рекурсивном использовании найденного им алгоритма умножения двух матриц порядка 2 с 7 умножениями, а не с 8, как в стандартном алгоритме. Можно обратить внимание на 2 особенности алгоритма Штрассена. Во-первых, на асимптотическую оценку сложности алгоритма умножения больших матриц, построенного рекурсивно, влияет только число умножений в алгоритме умножения маленьких матриц, используемых для рекурсии. Во-вторых, при рекурсии элементы маленьких матриц сами являются матрицами и поэтому могут не коммутировать между собой. Эти 2 осо- бенности породили исследования билинейной сложности умножения матриц и умножения в других алгебрах. В билинейных алгоритмах сначала должны вычисляться несколько произведений линейных комбинаций эле- ментов первого сомножителя на линейные комбинации элементов второго сомножителя. А затем из этих произведений линейными комбинациями должны получаться все требуемые выражения. При этом число произведений называют билинейной сложностью билинейного алгоритма, а мини- мум билинейной сложности по всем билинейным алгоритмам, решающим данную задачу, называют билинейной сложностью задачи. Установить точное значение билинейной сложности редко удается даже в задачах перемножения двух матриц малого размера. Например, для задачи перемножения двух матриц размера 3 × 3 к настоящему момен- ту известно только, что билинейная сложность заключена между 19 и 23 [4, 5]. Несложно установить точное значение билинейной сложности умножения двух матриц, если хотя бы в одной из них всего одна строка или один столбец. В данной работе исследуется билинейная сложность умножения матрицы размера m × 2 на матрицу размера 2 × 2 над произвольным полем. Точное значение билинейной сложности для умножения таких матриц над произвольным полем известно только при m = 2, 3, 4 [6, 7, 8]. Из результа- та Штрассена можно несложно получить, что билинейная сложность этой задачи не превосходит ⌈ 7m 2 ⌉ для произвольного поля. В работе [9] была по- лучена такая же нижняя оценка, но только для поля из 2 элементов. Для произвольных полей в работе [5] для этой задачи получена нижняя оценка 3m + 1. В данной статье доказано, что билинейная сложность умножения матрицы размера m×2 на матрицу размера 2×2 над произвольным полем при m ≥ 3 не может быть меньше чем 3m + 2.

1. Strassen V. Gaussian elimination is not optimal // Numer. Math. 1969. Vol. 13. P. 354–356. [Имеется перевод: Штрассен В. Алгоритм Гаусса не оптимален // Кибернетический сборник, вып. 7. М.: Мир, 1970. С. 67–70].

2. Burgisser P., Clausen M. Shokrollahi M. A. Algebraic Complexity Theory. Berlin: Springer-Verlag, 1997. 645p.

3. Coppersmith D., Winograd S. Matrix Multiplication via Arithmetic Progressions // J. Symbolic Computation. 1990. Vol. 9, №3. P. 251–280.

4. Laderman J. D. A noncommutative algorithm for multiplying 3 × 3 matrices using 23 multiplications // Bull. Amer. Math. Soc. 1976. Vol. 82, №1. P. 126– 128.

5. Bl¨aser M. On the complexity of the multiplication of matrices of small formats // J. Complexity. 2003. Vol. 19. P. 43–60.

6. Winograd S. On multiplication of 2 × 2 matrices // Linear Algebra and Appl. 1971. Vol. 4. P. 381–388.

7. Alekseyev V. B. On the complexity of some algorithms of matrix multiplication // Journal of Algorithms. 1985. Vol. 6, №1. P. 71–85.

8. Алексеев В.Б., Смирнов А.В. О точной и приближенной билинейных сложностях умножения матриц размеров 4 × 2 и 2 × 2 // Современные проблемы математики. 2013. Вып. 17. С. 135–152.

9. Hopcroft J. E., Kerr L.R. On minimizing the number of multiplications necessary for matrix multiplication // SIAM J. Appl. Math. 1971. Vol. 20, №1. P. 127–148.

10. Strassen V. Vermeidung von Divisionen // J. Reine und Angev. Math. 1973. Vol. 264. P. 184–202.

11. Макаров О. М. Некоммутативный алгоритм умножения квадратных матриц пятого порядка, использующий сто умножений // Журн. вычисл. математики и мат. физики. 1987. Т. 27, №2. С. 311–315.

12. Смирнов А. В. О билинейной сложности и практических алгоритмах умножения матриц // Журн. вычисл. математики и мат. физики. 2013. Т. 53, №12. С. 1970–1984.

13. Hopcroft J. E., Musinski J. Duality applied to the complexity of matrix multiplication and other bilinear forms // SIAM J. Comput. 1973. Vol. 2, №3. P. 159–173.

14. de Groote H. F. On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for 2 × 2 matrix multiplication // Theoret. Comput. Sci. 1978. Vol. 7, №2. P. 127–148.

15. Алексеев В. Б. О билинейной сложности умножения матриц размеров 5 × 2 и 2 × 2 // Ученые записки Казанского университета. Серия Физико-математические науки. 2014. Т. 156, №3. С. 19–29.