Strassen Matrix
Strassen's algorithm for matrix multiplication is a divide-and-conquer algorithm that reduces the number of multiplications from 8 to 7 for 2x2 blocks, achieving O(n^2.807) time instead of O(n³). It's efficient for large matrices but has higher constant factors.
The standard divide-and-conquer matrix multiplication divides each matrix into four submatrices, computes 8 products recursively, and combines. Strassen reduces to 7 products using clever formulas.
Outline of Strassen's 7 multiplications:
Let A = [[A11, A12], [A21, A22]], B = [[B11, B12], [B21, B22]].
Compute:
P1 = (A11 + A22)*(B11 + B22)
P2 = (A21 + A22)*B11
P3 = A11*(B12 - B22)
P4 = A22*(B21 - B11)
P5 = (A11 + A12)*B22
P6 = (A21 - A11)*(B11 + B12)
P7 = (A12 - A22)*(B21 + B22)
Then C11 = P1 + P4 - P5 + P7, etc.
Implementation is complex due to memory management; for most practical purposes, optimized libraries use block multiplication, but Strassen's insight is foundational.
Two Minute Drill
- Strassen's algorithm multiplies matrices in O(n^2.807).
- Uses divide and conquer with 7 multiplications instead of 8.
- Better for large n, but constant overhead.
- Foundation for more advanced matrix algorithms.
Need more clarification?
Drop us an email at career@quipoinfotech.com