Content deleted Content added
Wikified |
LouScheffer (talk | contribs) →Matrix multiplication: Add parenthesis to a parenthetical phrase |
||
Line 13:
=== Matrix multiplication ===
The first improvement over brute-force matrix multiplication (which needs <math>O(n^3)</math> multiplications) was the [[Strassen algorithm]]: a recursive algorithm that needs <math>O(n^{2.807})</math>multiplications. This algorithm is not galactic and is used in practice. Further extensions of this, using sophisticated group theory, are the [[Coppersmith–Winograd algorithm]] and its slightly better successors, needing <math>O(n^{2.373})</math> multiplications. These are galactic – "We nevertheless stress that such improvements are only of theoretical interest, since the huge constants involved in the complexity of fast matrix multiplication usually make these algorithms impractical."<ref>{{citation
| last = Le Gall | first = F.
| arxiv = 1204.1111
| |||