Lesson plan
Strassen algorithm
In linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm for matrix multiplication. It is faster than the standard matrix multiplication algorithm for large matrices, with a better asymptotic complexity ( O(n^{\log_2 7}) versus O(n^3) ), although the naive algorithm is often better for smaller matrices. The Strassen algorithm is slower than the fastest known algorithms for extremely large matrices, but such galactic algorithms are not useful in practice, as they are much slower for matrices of practical size. For small matrices, highly optimized implementations of the conventional algorithm are generally faster because Strassen's additional additions and recursion overhead outweigh its reduction in multiplications. Strassen's algorithm works for any ring such as plus/multiply, but not all semirings, particularly combinatorial matrix multiplication such as min-plus or boolean algebra, where the naive algorithm still works.
Article summary
In linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm for matrix multiplication. It is faster than the standard matrix multiplication algorithm for large matrices, with a better asymptotic complexity ( O(n^{\log_2 7}) versus O(n^3) ), although the naive algorithm is often better for smaller matrices. The Strassen algorithm is slower than the fastest known algorithms for extremely large matrices, but such galactic algorithms are not useful in practice, as they are much slower for matrices of practical size. For small matrices, highly optimized implementations of the conventional algorithm are generally faster because Strassen's additional additions and recursion overhead outweigh its reduction in multiplications. Strassen's algorithm works for any ring such as plus/multiply, but not all semirings, particularly combinatorial matrix multiplication such as min-plus or boolean algebra, where the naive algorithm still works.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.