Computational complexity of matrix multiplication: Difference between revisions

Revision as of 00:18, 6 October 2022

Revision as of 00:25, 6 October 2022

Line 68:

'''output''' ''C'' (as A*B)

This [[algorithm]] requires, in the [[worst-case complexity|worst case]], {{tmath|n^3}} multiplications of scalars and {{tmath|n^3 - n^2}} additions for computing the product of two square {{math|''n''×''n''}} matrices. Its [[computational complexity]] is therefore {{tmath|O(n^3)}}, in a [[model of computation]] where field operations (addition and multiplication) take constant time (in practice, this is the case for [[floating point]] numbers, but not necessarily for integers). This naive algorithm can be improved: number of multiplications can be reduced to 47 for n=4<ref>{{Cite journal |title=Extended Data Fig. 1: Algorithm for multiplying 4 × 4 matrices in modular arithmetic (\({{\mathbb{Z}}}_{2}\)) with 47 multiplications. {{!}} Nature |url=https://www.nature.com/articles/s41586-022-05172-4/figures/6?as=jpg |language=en}}</ref> and to 22 for commutative case<ref>{{cite web |title=О. М. Макаров, “Алгоритм умножения матриц размера $3\times 3$”, Ж. вычисл. матем. и матем. физ., 26:2 (1986), 293–294; Comput. Math. Math. Phys., 26:1 (1986), 179–180 |url=https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=4056&option_lang=rus |access-date=5 October 2022 |website=www.mathnet.ru}}</ref> for n=3 (and to 23 for non-commutative case<ref>{{Cite journal |last=Laderman |first=Julian D. |date=1976 |title=A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications |url=https://www.ams.org/bull/1976-82-01/S0002-9904-1976-13988-2/ |journal=Bulletin of the American Mathematical Society |language=en |volume=82 |issue=1 |pages=126–128 |doi=10.1090/S0002-9904-1976-13988-2 |issn=0002-9904}}</ref>).

=== Strassen's algorithm ===