Computational complexity of matrix multiplication: Difference between revisions

Revision as of 02:17, 28 December 2021

Revision as of 20:38, 28 December 2021

Line 239:

=== Lower bounds for ω ===

There is a trivial lower bound of {{tmath|\omega \ge 2}}. Since any algorithm for multiplying two {{math|''n'' × ''n''}}-matrices has to process all {{math|2''n''²}} entries, there is a trivial asymptotic lower bound of {{math|Ω(''n''²)}} operations for any matrix multiplication algorithm. Thus {{tmath|2\le \omega < 2.373}}. It is unknown whether {{tmath|\omega > 2}}. The best known lower bound for matrix-multiplication complexity is {{math|Ω(''n''² log(''n''))}}, for bounded coefficient [[Arithmetic circuit complexity|arithmetic circuits]] over the real or complex numbers, and is due to [[Ran Raz]].<ref>{{cite journal | last1 = Raz | first1 = Ran | author-link = Ran Raz | year = 2002| title = On the complexity of matrix product | journal = Proceedings of the Thirty-fourth Annual ACM Symposium on Theory of Computing | pages = 144 | doi = 10.1145/509907.509932 | isbn = 1581134959 | s2cid = 9582328 }}</ref> For specific cases of fields such as integers, floating point numbers and complex numbers, a quadratic-time algorithm has been proposed that uses a bitwise convolutional number-theoretic method.<ref>{{cite arXiv |last= Mohapatra |first= Shrohan|author-link= Shrohan Mohapatra|eprint= 1806.03701 |title= A new quadratic-time number-theoretic algorithm to solve matrix multiplication problem |class=cs.DS |date= 2019}}</ref>

=== Rectangular matrix multiplication ===