The Strassen algorithm, named after Volker Strassen, is a method for multiplying two matrices that is asymptotically faster than the standard matrix multiplication algorithm for large matrices, achieving a complexity of approximately O(n to the power 2.807) against the standard method's O(n cubed). Strassen first published the algorithm in 1969, demonstrating for the first time that the conventional cubic-time approach to matrix multiplication was not optimal, though the algorithm's extra matrix additions and subtractions make it less efficient than the standard method in practice for smaller matrices. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Time ComplexityO(n^log2(7)), approximately O(n^2.8074), versus the standard O(n^3). 1 Classification
Design Technique Time Complexity
Time Complexity (category) Connections
Credited To
Source Wikipedia: Strassen's Algorithm
In Field
Source Wikipedia: Strassen's Algorithm
Invented By
Volker Strassen published his subcubic matrix multiplication algorithm in 1969, the first to beat the standard cubic-time method.
Uses Design Technique
Sources
1. Wikipedia: Strassen's Algorithm
Wikimedia FoundationLead section
a better asymptotic complexity (O(n^log2(7)) versus O(n^3))
Body, history
Volker Strassen first published this algorithm in 1969, demonstrating that the standard n^3 general matrix multiplication approach was suboptimal.
- Strassen: Algorithm section recursively splits matrices into submatrix products
In Field: Algorithms and Complexity Theory, Lead sentence
Strassen algorithm, named after Volker Strassen, is an algorithm for matrix multiplication.
Credited To: Volker Strassen, Lead sentence
Strassen algorithm, named after Volker Strassen, is an algorithm for matrix multiplication.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.