The bilinear complexity and practical algorithms for matrix multiplication

A. V. Smirnov

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 53 (2013) no. 12, pp. 1970-1984

Résumé

A method for deriving bilinear algorithms for matrix multiplication is proposed. New estimates for the bilinear complexity of a number of problems of the exact and approximate multiplication of rectangular matrices are obtained. In particular, the estimate for the boundary rank of multiplying $3\times 3$ matrices is improved and a practical algorithm for the exact multiplication of square $n\times n$ matrices is proposed. The asymptotic arithmetic complexity of this algorithm is $O(n^{2.7743})$.

Bibliographie

[1] Strassen V., “Gaussian elimination is not optimal”, Numer. Math., 13 (1969), 354–356 | DOI | MR | Zbl

[2] Coppersmith D., Winograd S., “Matrix multiplication via arithmetic progressions”, J. Symbolic Comput., 9 (1990), 251–280 | DOI | MR | Zbl

[3] Hunold S., Rauber T., Runger G., “Combining building blocks for parallel multi-level matrix multiplication”, Parallel comput., 34:6–8 (2008), 411–426 | DOI | MR

[4] Kaporin I., “The aggregation and cancellation techniques as a practical tool for faster matrix multiplication”, Theor. Comput. Sci., 315:2–3 (2004), 469–510 | DOI | MR | Zbl

[5] Laderman J., Pan V. Y., Sha X.-H., “On practical algorithms for accelerated matrix multiplication”, Linear Algebra Appls., 162–164 (1992), 557–588 | DOI | MR | Zbl

[6] Schönhage A., “Partial and total matrix multiplication”, SIAM J. Comput., 10:3 (1981), 434–455 | DOI | MR | Zbl

[7] Sen S. K., “Open problems in computational linear algebra”, Nonlinear Analys., 63:5–7 (2005), 926–934 | DOI | MR | Zbl

[8] “Slozhnost umnozheniya matrits. Obzor”, Kibernetich. sbornik, 1988, no. 25, 139–236

[9] Landsberg J. M., “Geometry and the complexity of matrix multiplication”, Bull. Amer. Math. Soc., 45 (2008), 247–284 | DOI | MR | Zbl

[10] Brent R. P., Algorithms for matrix multiplications, Comput. Sci. Dept. Report CS 157, Stanford University, 1970

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

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

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

[14] Johnson R. W., McLoughlin A. M., “Noncommutative bilinear algorithms for $3\times3$ matrix multiplication”, SIAM J. Comput., 15:2 (1986), 595–603 | DOI | MR | Zbl

[15] Makarov O. M., “Nekommutativnyi algoritm umnozheniya kvadratnykh matrits pyatogo poryadka, ispolzuyuschii sto umnozhenii”, Zh. vychisl. matem. i matem. fiz., 27:2 (1987), 311–315 | MR | Zbl

[16] Bini D., “Relations between exact and approximate bilinear algorithms, applications”, Calcolo, 17 (1980), 87–97 | DOI | MR | Zbl

[17] Bakhvalov N. S., Chislennye metody, Nauka, M., 1975

[18] Bini D., Capovani M., Lotti G., Romani F., “$O(n^{2.7799})$ complexity for approximate matrix multiplication”, Inform. Process. Lett., 8:5 (1979), 234–235 | DOI | MR | Zbl

[19] Alekseev V. B., Smirnov A. V., “O tochnoi i priblizhennoi bilineinykh slozhnostyakh umnozheniya matrits razmerov $4\times 2$ i $2\times2$”, Matematika i informatika, v. 2, Sovr. probl. matem., 17, K 75-letiyu so dnya rozhdeniya Anatoliya Alekseevicha Karatsuby, MIAN, M., 2013, 135–152 | DOI

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

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

[22] Bini D., Lotti G., “Stability of fast algorithms for matrix multiplication”, Numer. Math., 36 (1980), 63–72 | DOI | MR | Zbl