Powers of tensors and fast matrix multiplication
作者： François Le Gall
关键词:
摘要: This paper presents a method to analyze the powers of given trilinear form (a special kind algebraic construction also called tensor) and obtain upper bounds on asymptotic complexity matrix multiplication. Compared with existing approaches, this is based convex optimization, thus has polynomial-time complexity. As an application, we use study by Coppersmith Winograd [Journal Symbolic Computation, 1990] bound ω
acm.org
harvard.edu
core.ac.uk
arxiv-vanity.com参考文章(16)
Francois Le Gall, Faster Algorithms for Rectangular Matrix Multiplication 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. pp. 514- 523 ,(2012) , 10.1109/FOCS.2012.80
B. Szegedy, C. Umans, R. Kleinberg, H. Cohn, Group-theoretic algorithms for matrix multiplication foundations of computer science. pp. 379- 388 ,(2005) , 10.1109/SFCS.2005.39
Noga Alon, Amir Shpilka, Christopher Umans, On sunflowers and matrix multiplication Computational Complexity. ,vol. 22, pp. 219- 243 ,(2013) , 10.1007/S00037-013-0060-1
Stephen Boyd, Lieven Vandenberghe, Convex Optimization Cambridge University Press. ,(2004)
Markus Blaeser, Fast Matrix Multiplication Theory of Computing. ,vol. 5, pp. 1- 60 ,(2013) , 10.4086/TOC.GS.2013.005
Andrew James Stothers, On the complexity of matrix multiplication The University of Edinburgh. ,(2010)
Shu-Cherng Fang, Jacob H.-S. Tsao, Entropy Optimization: Interior Point Methods Encyclopedia of Optimization. ,vol. 2, pp. 907- 912 ,(2001)
Mohammad A. Shokrollahi, Michael Clausen, Peter Brgisser, Algebraic Complexity Theory ,(1996)
Aharon Ben-Tal, Arkadi Nemirovski, Lectures on modern convex optimization: analysis, algorithms, and engineering applications Society for Industrial and Applied Mathematics. ,(2001) , 10.1137/1.9780898718829
Christopher Umans, Henry Cohn, Fast matrix multiplication using coherent configurations symposium on discrete algorithms. pp. 1074- 1086 ,(2013) , 10.5555/2627817.2627894