Computational complexity of matrix multiplication: Difference between revisions

Revision as of 08:55, 1 October 2022

Revision as of 22:52, 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 23 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 ===