An Introduction to the Computational Complexity of Matrix Multiplication

doi:10.1007/s40305-019-00280-x

Journal of the Operations Research Society of China ›› 2020, Vol. 8 ›› Issue (1): 29-43.doi: 10.1007/s40305-019-00280-x

收稿日期:2018-10-09 修回日期:2019-02-26 出版日期:2020-03-30 发布日期:2020-02-18
通讯作者: Sheng-Long Hu, Yan Li, Jie Wang, Zheng-Hai Huang E-mail:shenglonghu@hdu.edu.cn;yanlee@tju.edu.cn;jiewang@cjlu.edu.cn;huangzhenghai@tju.edu.cn
基金资助:
This work was partially supported by the National Natural Science Foundation of China (Nos. 11431002, 11771328, 11871051), Young Elite Scientists Sponsorship Program by Tianjin, the Natural Science Foundation of Zhejiang Province (No. LD19A010002), and Innovation Research Foundation of Tianjin University (No. 2017XRG-0015).

An Introduction to the Computational Complexity of Matrix Multiplication

Yan Li¹, Sheng-Long Hu², Jie Wang³, Zheng-Hai Huang¹

1 School of Mathematics, Tianjin University, Tianjin 300350, China;
2 Department of Mathematics, School of Science, Hangzhou Dianzi University, Hangzhou 310018, China;
3 College of Science, China Jiliang University, Hangzhou 310018, China

Received:2018-10-09 Revised:2019-02-26 Online:2020-03-30 Published:2020-02-18
Contact: Sheng-Long Hu, Yan Li, Jie Wang, Zheng-Hai Huang E-mail:shenglonghu@hdu.edu.cn;yanlee@tju.edu.cn;jiewang@cjlu.edu.cn;huangzhenghai@tju.edu.cn

摘要/Abstract

Abstract: This article introduces the approach on studying the computational complexity of matrix multiplication by ranks of the matrix multiplication tensors. Basic results and recent developments in this area are reviewed.

Key words: Matrix multiplication, Computational complexity, Tensor rank, Bilinear mapping, Border rank

中图分类号:

. [J]. Journal of the Operations Research Society of China, 2020, 8(1): 29-43.

Yan Li, Sheng-Long Hu, Jie Wang, Zheng-Hai Huang. An Introduction to the Computational Complexity of Matrix Multiplication[J]. Journal of the Operations Research Society of China, 2020, 8(1): 29-43.

参考文献

[1] Golub, G.H., Van Loan, C.F.:Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013)
[2] Bürgisser, P., Clausen, M., Shokrollahi, M.A.:Algebraic Complexity Theory. Grundlehren der Mathematischen Wissenschaften, vol. 315. Springer-Verlag, Berlin (1997)
[3] Strassen, V.:Gaussian elimination is not optimal. Numer. Math. 13, 354-356(1969)
[4] Le Gall, F.:Powers of tensors and fast matrix multiplication. In:Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pp. 296-303. Association for Computing Machinery, New York (2014)
[5] Landsberg, J.M.:Tensors:Geometry and Applications. American Mathematical Society, Providence (2012)
[6] Winograd, S.:On multiplication of 2×2 matrices. Linear Algebra Appl. 4, 381-388(1971)
[7] Laderman, J.D.:A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications. Bull. Am. Math. Soc. 82, 126-128(1976)
[8] Gastinel, N.:Sur le calcul des produits de matrices. Numer. Math. 17, 222-229(1971)
[9] Hopcroft, J., Musinski, J.:Duality applied to the complexity of matrix multiplication and other bilinear forms. SIAM J. Comput. 2, 159-173(1973)
[10] Pan, V.Y.:Strassen's algorithm is not optimal trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations. In:Proceedings of the 19th Annual Symposium on Foundations of Computer Science, pp. 166-176. IEEE Computer Society, Washington (1978)
[11] Bini, D., Capovani, M., Romani, F., Lotti, G.:O(n^2.7799) complexity for n×n approximate matrix multiplication. Inf. Process. Lett. 8, 234-235(1979)
[12] Schonhage, A.:Partial and total matrix multiplication. SIAM J. Comput. 10, 434-455(1981)
[13] Pan, V.Y.:Field extension and trilinear aggregating, uniting and canceling for the acceleration of matrix ultiplications. In:Proceedings of 20th Annual Symposium on FOCS, pp. 28-38(1979)
[14] Romani, F.:Some properties of disjoint sums of tensors related to matrix multiplication. SIAM J. Comput. 11, 263-267(1982)
[15] Coppersmith, D., Winograd, S.:On the asymptotic complexity of matrix multiplication. SIAM J. Comput. 11, 472-492(1982)
[16] Strassen, V.:The asymptotic spectrum of tensors and the exponent of matrix multiplication. In:Proceedings of the 27th Annual Symposium on Foundations of Computer Science, pp. 49-54(1986)
[17] Coppersmith, D., Winograd, S.:Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 251-280(1990)
[18] Stothers, A.:On the complexity of matrix multiplication. Ph.D. thesis, University of Edinburgh (2010)
[19] Williams, V.V.:Multiplying matrices faster than Coppersmith-Winograd. In:Proceedings of the 44th ACM Symposium on Theory of Computing, pp. 887-898(2012)
[20] Williams, V. V.:Multiplying matrices faster than Coppersmith-Winograd. Version available at http://theory.stanford.edu/~virgi/matrixmult-f.pdf.Retrieved on 30 Jan 2014
[21] Cohn, H., Kleinberg, R., Szegedy, B., Umans, C.:Group-theoretic algorithms for matrix multiplication. In:Proceedings of the 46th Annual Symposium on Foundations of Computer Science 9-12 July, Genova, Italy, pp. 379-388. IEEE Computer Society (2006)
[22] Alon, N., Shpilka, A., Umans, C.:On sunflowers and matrix multiplication. Comput. Complex. 22, 219-243(2013)
[23] Erdős, P., Rado, R.:Intersection theorems for systems of sets. J. Lond. Math. Soc. 35, 85-90(1960)
[24] Strassen, V.:Rank and optimal computation of generic tensors. Linear Algebra Appl. 52(53), 645-685(1983)
[25] Håstad, J.:Tensor rank is NP-complete. J. Algorithms 11, 644-654(1990)
[26] Gonzalez,T.,Ja'Ja,J.:On the complexity of computing bilinear forms with{0, 1}constants.J.Comput. Syst. Sci. 20, 77-95(1980)
[27] Bläser, M.:Lower bounds for the multiplicative complexity of matrix multiplication. Comput. Complex. 8, 203-226(1999)
[28] Bläser, M.:On the complexity of the multiplication of matrices of small formats. J. Complex. 19, 43-60(2003)
[29] Bläser, M.:A 5/2n²-lower bound for the rank of n×n-matrix multiplication over arbitrary fields. In:40th Annual Symposium on Foundations of Computer Science (New York, 1999), pp. 45-50. IEEE Computer Society, Los Alamitos, CA (1999)
[30] Landsberg, J.M.:New lower bounds for the rank of matrix multiplication. SIAM J. Comput. 43, 144-149(2014)
[31] Massarenti, A., Raviolo, E.:The rank of n×n matrix multiplication is at least 3n²-2√2n^3/2-3n. Linear Algebra Appl. 438, 4500-4509(2013)
[32] Alekseyev, V.B.:On the complexity of some algorithms of matrix multiplication. J. Algorithms 6, 71-85(1985)
[33] Hopcroft, J., Kerr, L.:On minimizing the number of multiplications necessary for matrix multiplication. SIAM J. Appl. Math. 20, 30-36(1971)
[34] Bini, D.:Relations between exact and approximate bilinear algorithms. Applications. Calcolo 17, 87-97(1980)
[35] Lickteig, T.:A note on border rank. Inform. Process. Lett. 18, 173-178(1984)
[36] Landsberg,J.M.,Ottaviani,G.:Newlower boundsfor theborder rank of matrix multiplication.Theory Comput. 11, 285-298(2015)
[37] Smirnov, A.V.:The bilinear complexity and practical algorithms for matrix multiplication. Comput. Math. Math. Phys. 53, 1781-1795(2013)
[38] Landsberg, J.M.:The border rank of the multiplication of 2×2 matrices is seven. J. Am. Math. Soc. 19, 447-459(2006)
[39] Landsberg, J.M., Michalek, M.:On the geometry of border rank algorithms for matrix multiplication and other tensors with symmetry. SIAM J. Appl. Algebra Geom. 1(1), 2-19(2017)
[40] Smirnov, A.V.:The approximate bilinear algorithm of length 46 for multiplication of 4×4 matrices. arXiv:1412.1687(2014)
[41] Landsberg, J.M., Michalek, M.:A 2n²-log₂ n-1 lower bound for the border rank of matrix multiplication. Int. Math. Res. Not. IMRN 15, 4722-4733(2018)
[42] Lickteig, T.:Typical tensorial rank. Linear Algebra Appl. 69, 95-120(1985)
[43] Jacob, R., Stöckel, M.:Fast Output-Sensitive Matrix Multiplication. Lecture Notes in Computer Science, vol. 9294, pp. 766-778. Springer, Heidelberg (2015)

An Introduction to the Computational Complexity of Matrix Multiplication

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价