×

On the complexity of the multiplication of matrices of small formats. (English) Zbl 1026.68062

Summary: We prove a lower bound of \(2mn+2n-m-2\) for the bilinear complexity of the multiplication of \(n \times m\)-matrices with \(m\times n\)-matrices using the substitution method (\(m\geqslant n\geqslant 3\)). In particular, we obtain the improved lower bound of 19 for the bilinear complexity of \(3\times 3\)-matrix multiplication.

MSC:

68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alder, A.; Strassen, V., On the algorithmic complexity of associative algebras, Theoret. Comput. Sci., 15, 201-211 (1981) · Zbl 0464.68045
[2] Bini, D.; Capovani, M.; Lotti, G.; Romani, F., \(O(n^{2.7799})\) complexity for matrix multiplication, Inform. Process. Lett., 8, 234-235 (1979) · Zbl 0395.68048
[3] M. Bläser, A \(52^2nn\); M. Bläser, A \(52^2nn\)
[4] Bläser, M., Lower bounds for the multiplicative complexity of matrix multiplication, Comput. Complexity, 8, 203-226 (1999) · Zbl 0966.68227
[5] Bläser, M., Lower bounds for the bilinear complexity of associative algebras, Comput. Complexity, 9, 73-112 (2000) · Zbl 0970.68069
[6] Brockett, R. W.; Dobkin, D., On the optimal evaluation of a set of bilinear forms, Linear Algebra Appl., 19, 207-235 (1978) · Zbl 0376.68042
[7] Bürgisser, P.; Clausen, M.; Shokrollahi, M. A., Algebraic Complexity Theory (1997), Springer: Springer Berlin · Zbl 1087.68568
[8] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progression, J. Symbolic Comput., 9, 251-280 (1990) · Zbl 0702.65046
[9] de Groote, H. F., On the varieties of optimal algorithms for the computation of bilinear mappingsoptimal algorithms for 2×2-matrix multiplication, Theoret. Comput. Sci., 7, 127-148 (1978) · Zbl 0418.68037
[10] de Groote, H. F., On the varieties of optimal algorithms for the computation of bilinear mappingsthe isotropy group of a bilinear mapping, Theoret. Comput. Sci., 7, 1-24 (1978) · Zbl 0418.68036
[11] H.F. de Groote, Lectures on the Complexity of Bilinear Problems, Lecture Notes in Computer Science, Vol. 245, Springer, Berlin, 1986.; H.F. de Groote, Lectures on the Complexity of Bilinear Problems, Lecture Notes in Computer Science, Vol. 245, Springer, Berlin, 1986. · Zbl 0609.68032
[12] Hopcroft, J. E.; Kerr, L. R., On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math., 20, 20-36 (1971) · Zbl 0215.55501
[13] Johnson, R. W.; McLoughlin, A. M., Noncommutative bilinear algorithms for 3×3 matrix multiplication, SIAM J. Comput., 15, 2, 595-603 (1986) · Zbl 0622.68037
[14] Laderman, J., A noncommutative algorithm for multiplying 3×3-matrices using 23 multiplications, Bull. Amer. Math. Soc., 82, 180-182 (1976)
[15] Pan, V. Ya., Methods for computing values of polynomials, Russian Math. Surveys, 21, 105-136 (1966)
[16] Schönhage, A., Partial and total matrix multiplication, SIAM J. Comput., 10, 434-455 (1981) · Zbl 0462.68018
[17] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356 (1969) · Zbl 0185.40101
[18] Strassen, V., Relative bilinear complexity and matrix multiplication, J. Reine Angew. Math., 375/376, 406-443 (1987) · Zbl 0621.68026
[19] Waksman, A., On Winograd’s algorithm for inner products, IEEE Trans. Comput., C-19, 360-361 (1970) · Zbl 0196.17104
[20] Winograd, S., On multiplication of 2×2-matrices, Linear Algebra Appl., 4, 381-388 (1971) · Zbl 0225.68018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.