Scribd
Upload
9 views10 pages

Strassen's Efficient Matrix Multiplication

Strassen's Matrix Multiplication improves the traditional O(n^3) matrix multiplication algorithm by using a divide-and-conquer approach that reduces the number of multiplications from 8 to 7, resulting in a time complexity of O(n^2.81). The algorithm involves dividing matrices into submatrices and recursively calculating products, but it has practical limitations such as larger constant factors and numerical instability. Despite its efficiency, faster algorithms exist, with the best known being O(n^2.3727).

Uploaded by

sandeepkumar9719090036
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views10 pages

Strassen's Efficient Matrix Multiplication

Strassen's Matrix Multiplication improves the traditional O(n^3) matrix multiplication algorithm by using a divide-and-conquer approach that reduces the number of multiplications from 8 to 7, resulting in a time complexity of O(n^2.81). The algorithm involves dividing matrices into submatrices and recursively calculating products, but it has practical limitations such as larger constant factors and numerical instability. Despite its efficiency, faster algorithms exist, with the best known being O(n^2.3727).

Uploaded by

sandeepkumar9719090036
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Strassen’s Matrix Multiplication

Andreas Klappenecker

[partially based on slides by Prof. Welch]


Matrix Multiplication
Consider two n x n matrices A and B

Recall that the matrix product C = AB of two n x n matrices is defined


as the n x n matrix that has the coefficient
ckl = ∑m akm bml
in row k and column l, where the sum ranges over the integers from 1
to n; the scalar product of the kth row of a with the lth column of B.

The straightforward algorithm uses O(n3) scalar operations.


Can we do better?
Idea: Use Divide and Conquer

The divide and conquer paradigm is important general technique


for designing algorithms. In general, it follows the steps:

- divide the problem into subproblems

- recursively solve the subproblems

- combine solutions to subproblems to get solution to original


problem
Divide-and-Conquer

Let write the product A B = C as follows:

A0 A1 B0 B1 A0×B0+A1×B2 A0×B1+A1×B3
× =
A2 A3 B2 B3 A2×B0+A3×B2 A2×B1+A3×B3

• Divide matrices A and B into four submatrices each

• We have 8 smaller matrix multiplications and 4 additions. Is it faster?


Divide-and-Conquer
Let us investigate this recursive version of the matrix
multiplication.

Since we divide A, B and C into 4 submatrices each, we can


compute the resulting matrix C by

• 8 matrix multiplications on the submatrices of A and B,

• plus Θ(n2) scalar operations


Divide-and-Conquer

• Running time of recursive version of straightfoward algorithm is

T(n) = 8T(n/2) + Θ(n2) and T(2) = Θ(1)

where T(n) is running time on an n x n matrix

• Master theorem gives us:

T(n) = Θ(n3)

• Can we do fewer recursive calls (fewer multiplications of the n/2 x


n/2 submatrices)?
Strassen’s Matrix Multiplication
A × B = C .
A11 A12 B11 B12 C11 C12

A21 A22
×
B21 B22
= C21 C22

P1 = (A11+ A22)(B11+B22)
P2 = (A21 + A22) * B11 C11 = P1 + P4 - P5 + P7
P3 = A11 * (B12 - B22) C12 = P3 + P5
P4 = A22 * (B21 - B11) C21 = P2 + P4
P5 = (A11 + A12) * B22 C22 = P1 + P3 - P2 + P6
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)
Strassen's Matrix Multiplication

• Strassen found a way to get all the required information with only
7 matrix multiplications, instead of 8.

• Recurrence for new algorithm is

• T(n) = 7T(n/2) + Θ(n2)


Solving the Recurrence Relation

Applying the Master Theorem to

T(n) = a T(n/b) + f(n)

with a=7, b=2, and f(n)=Θ(n2).

Since f(n) = O(nlogb(a)-ε) = O(nlog2(7)-ε),

case a) applies and we get

T(n)= Θ(nlogb(a)) = Θ(nlog2(7)) = O(n2.81).


Discussion of Strassen's Algorithm
• Not always practical
• constant factor is larger than for naïve method

• specially designed methods are better on sparse matrices

• issues of numerical (in)stability

• recursion uses lots of space

• Not the fastest known method


• Fastest known is O(n2.3727) [Winograd-Coppersmith algorithm improved by V.
Williams]

• Best known lower bound is Ω(n2)

You might also like