On bilinear complexity of multiplication of $m\times 2$ and $2\times 2$ matrices

V. B. Alekseev

Čebyševskij sbornik, Tome 16 (2015) no. 4, pp. 11-27.

Résumé

In this paper we investigate the complexity of matrix multiplication. V. Strassen in 1969 [1] constructed an algorithm to multiply two matrices of order $n$ with the number of arithmetic operations $O\left( n^{\log_27}\right) $, which is asymptotically better than the complexity of the order $n^3$ of standard matrix multiplication algorithm “line by column”. In subsequent years, active investigations were carried on minimal complexity of various algebraic operations. The results of the researches in this field are well reflected in the book [2]. The situation in the problem of matrix multiplication is quite hard. By the end of the 1980s, with the efforts of many mathematicians complexity of matrix multiplication was reduced to $O\left( n^{2.38}\right) $ [3], but since then there is no significant progress in this problem. In order to better understand the problems associated with finding fast algorithms for matrix multiplication, this problem is investigated in different directions. One such area is the study minimal complexity of matrix multiplication for small sizes. This study is of interest in itself, but is also linked to the fact that the fast algorithms for matrix multiplication of small size can be recursively used for matrix multiplication of large size. In particular, Strassen's algorithm uses recursively algorithm for multiplication of two matrices of order 2 with 7 multiplications rather than 8 as in standard algorithm. One can note two special properties of Strassen's algorithm. Firstly, only the number of multiplications in the algorithm for multiplication of small matrices used for recursion affects the asymptotic complexity of algorithm for multiplication of large matrices. Secondly, matrix elements in recursion are themselves matrices and therefore they do not commute. These two properties have generated studies of bilinear complexity of multiplication of matrices and multiplication in other algebras. The bilinear algorithm must first calculate several products of linear combination of the elements of the first factor by linear combination of the elements of the second factor. Then, all the required expressions must be obtained by linear combinations of these products. The number of products is called bilinear complexity of the algorithm, and the minimum bilinear complexity of all bilinear algorithms that solve this problem is called the bilinear complexity of the problem. It is rather difficult to establish the exact value of the bilinear complexity even for multiplication of two matrices of small size. For example, for the problem of multiplying two $3\times 3$ matrices so far we only know that the bilinear complexity lies between 19 and 23 [4, 5]. It is not difficult to establish the exact value of the bilinear complexity of multiplication of two matrices if at least one of them is only one row or one column. In this paper we investigate the bilinear complexity of multiplication of matrix of size $m\times 2$ by matrix of size $2\times 2$ over an arbitrary field. The exact value for the bilinear complexity for the multiplication of such matrices over an arbitrary field is known only when $m = 2, 3, 4$ [6, 7, 8]. From the result of Strassen it can be easy to get that the bilinear complexity of this problem does not exceed $\lceil\frac{7m}{2}\rceil$ for an arbitrary field. The same lower bound was obtained in the paper [9], but only for the field with two elements. For arbitrary fields the lower bound $3m+1$ for this problem was obtained in [5]. In this article it is proved that for $m\geq 3$ the bilinear complexity of multiplication of $m\times 2$ matrix by $2\times 2$ matrix over an arbitrary field can not be less than $3m+2$. Bibliography: 15 titles.

Détail

Keywords: matrix, matrix multiplication, algorithm, complexity, bilinear complexity.

Bibliographie

[1] Strassen V., “Gaussian elimination is not optimal”, Numer. Math., 13 (1969), 354–356 ; Shtrassen V., “Algoritm Gaussa ne optimalen”, Kiberneticheskii sbornik, 7, Mir, M., 1970, 67–70 | DOI | MR | Zbl

[2] Burgisser P., Clausen M., Shokrollahi M. A., Algebraic Complexity Theory, Springer-Verlag, Berlin, 1997, 645 pp. | MR | Zbl

[3] Coppersmith D., Winograd S., “Matrix Multiplication via Arithmetic Progressions”, J. Symbolic Computation, 9:3 (1990), 251–280 | DOI | MR | Zbl

[4] Laderman J. D., “A noncommutative algorithm for multiplying $3\times 3$ matrices using 23 multiplications”, Bull. Amer. Math. Soc., 82:1 (1976), 126–128 | DOI | MR | Zbl

[5] Bläser M., “On the complexity of the multiplication of matrices of small formats”, J. Complexity, 19 (2003), 43–60 | DOI | MR | Zbl

[6] Winograd S., “On multiplication of $2\times 2$ matrices”, Linear Algebra and Appl., 4 (1971), 381–388 | DOI | MR | Zbl

[7] Alekseyev V. B., “On the complexity of some algorithms of matrix multiplication”, Journal of Algorithms, 6:1 (1985), 71–85 | DOI | MR | Zbl

[8] Alekseev V. B., Smirnov A. V., “On exact and approximate bilinear complexities of multiplication of $4\times 2$ and $2\times 2$ matrices”, Proceedings of the Steklov Institute of Mathematics, 282, Suppl. 1 (2013), S123–S139 | DOI | DOI | MR | Zbl

[9] Hopcroft J. E., Kerr L. R., “On minimizing the number of multiplications necessary for matrix multiplication”, SIAM J. Appl. Math., 20:1 (1971), 127–148 | DOI | MR

[10] Strassen V., “Vermeidung von Divisionen”, J. Reine und Angev. Math., 264 (1973), 184–202 | MR | Zbl

[11] Makarov O. M., “Noncommutative algorithm for multiplying square matrices of order 5 using 100 multiplications”, Computational Mathematics and Mathematical Physics, 27:2 (1987), 311–315 (in Russian) | MR | Zbl

[12] Smirnov A. V., “The bilinear complexity and practical algorithms for matrix multiplication”, Computational Mathematics and Mathematical Physics, 53:12 (2013), 1781–1795 | DOI | DOI | MR | Zbl

[13] Hopcroft J. E., Musinski J., “Duality applied to the complexity of matrix multiplication and other bilinear forms”, SIAM J. Comput., 2:3 (1973), 159–173 | DOI | MR | Zbl

[14] de Groote H. F., “On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for $2\times 2$ matrix multiplication”, Theoret. Comput. Sci., 7:2 (1978), 127–148 | DOI | MR | Zbl

[15] Alekseev V. B., “On bilinear complexity of multiplication of $5\times 2$ and $2\times 2$ matrices”, Uchenye Zapiski Kazanskogo Universiteta. Serija Fiziko-matematicheskie Nauki, 156:3 (2014), 19–29 (in Russian)