"A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in practice."

Strassen algorithm works in $O(n^{2.8074})$. There is also the Coppersmith–Winograd algorithm which runs in $O(n^{2.37188})$,but it's a galactic algorithm. Are there any algorithms that outperform the Strassen algorithm with matrices smaller enough to be of any practical use?

  • $\begingroup$ Just a comment. Assuming an overhead factor $c$ of Strassen's, the breakeven occurs where $n^3=cn^{2.8074}$, or $n=c^{5.2}$. This shows how sensitive Strassens's algorithm is to overhead (and cache friendliness). $\endgroup$
    – user16034
    Jul 5, 2023 at 7:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.