Computational complexity of matrix multiplication: Difference between revisions

Revision as of 23:44, 5 October 2022

Revision as of 23:44, 5 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. 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<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 |website=www.mathnet.ru |access-date=5 October 2022}}</ref> for n=3. 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).

=== Strassen's algorithm ===