首页    期刊浏览 2024年10月04日 星期五
登录注册

文章基本信息

  • 标题:Fast Matrix Multiplication: Limitations of the Laser Method
  • 本地全文:下载
  • 作者:Andris Ambainis ; Yuval Filmus ; Francois Le Gall
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2014
  • 卷号:2014
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Until a few years ago, the fastest known matrix multiplication algorithm, due to Coppersmith and Winograd (1990), ran in time O ( n 2 3755 ) . Recently, a surge of activity by Stothers, Vassilevska-Williams, and Le Gall has led to an improved algorithm running in time O ( n 2 3729 ) . These algorithms are obtained by analyzing higher and higher tensor powers of a certain identity of Coppersmith and Winograd. We show that this exact approach cannot result in an algorithm with running time O ( n 2 3725 ) , and identify a wide class of variants of this approach which cannot result in an algorithm with running time O ( n 2 3078 ) ; in particular, this approach cannot prove the conjecture that for every 0"> 0 , two n n matrices can be multiplied in time O ( n 2+ ) . We describe a new framework extending the original laser method, which is the method underlying the previously mentioned algorithms. Our framework accommodates the algorithms by Coppersmith and Winograd, Stothers, Vassilevska-Williams and Le Gall. We obtain our main result by analyzing this framework. The framework is also the first to explain why taking tensor powers of the Coppersmith-Winograd identity results in faster algorithms.

  • 关键词:laser method ; lower bounds ; matrix multiplication
国家哲学社会科学文献中心版权所有