Scribd
Upload
371 views2 pages

Strassen Algorithm

Strassen algorithm is a faster way to multiply matrices compared to the standard algorithm. It was published in 1969 by Volker Strassen and uses 7 multiplications instead of 8 to multiply 2x2 matrices. While only slightly faster, it started the search for even more efficient matrix multiplication algorithms. Practical implementations switch to standard methods for small submatrices where those are more efficient, with the crossover point where Strassen is better depending on the implementation and hardware, estimated between 32-128 historically but now much larger due to optimizations of standard multiplication.

Uploaded by

Nilayan Ahmed
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
371 views2 pages

Strassen Algorithm

Strassen algorithm is a faster way to multiply matrices compared to the standard algorithm. It was published in 1969 by Volker Strassen and uses 7 multiplications instead of 8 to multiply 2x2 matrices. While only slightly faster, it started the search for even more efficient matrix multiplication algorithms. Practical implementations switch to standard methods for small submatrices where those are more efficient, with the crossover point where Strassen is better depending on the implementation and hardware, estimated between 32-128 historically but now much larger due to optimizations of standard multiplication.

Uploaded by

Nilayan Ahmed
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 algorithm

From Wikipedia, the free encyclopedia


In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used
for matrix multiplication. It is faster than the standard matrix multiplication algorithm and is useful in practice for large
matrices, but would be slower than the fastest known algorithm for extremely large matrices.
Contents
1 History
2 Algorithm
3 Asymptotic complexity
3.1 Rank or bilinear complexity
4 Implementation considerations
5 See also
6 References
7 External links
History
Volker Strassen published the Strassen algorithm in 1969. Although his algorithm is only slightly faster than the standard
algorithm for matrix multiplication, he was the first to point out that the standard approach is not optimal. His paper started
the search for even faster algorithms such as the more complex CoppersmithWinograd algorithm published in 1987.
Algorithm
The left column represents 2x2 matrix multiplication. Nave matrix multiplication requires one multiplication for each "1" of the left
column. Each of the other columns represents a single one of the 7 multiplications in the algorithm, and the sum of the columns gives the
full matrix multiplication on the left.
Let A, B be two square matrices over a ring R. We want to calculate the matrix product C as
If the matrices A, B are not of type 2
n
x 2
n
we fill the missing rows and columns with zeros.
We partition A, B and C into equally sized block matrices
with
then
With this construction we have not reduced the number of multiplications. We still need 8 multiplications to calculate the C
i,j
matrices, the same number of multiplications we need when using standard matrix multiplication.
Now comes the important part. We define new matrices
only using 7 multiplications (one for each M
k
) instead of 8. We may now express the C
i,j
in terms of M
k
, like this:
We iterate this division process n times (recursively) until the submatrices degenerate into numbers (elements of the ring R).
The resulting product will be padded with zeroes just like A and B, and should be stripped of the corresponding rows and
columns.
Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough
submatrices, for which those algorithms are more efficient. The particular crossover point for which Strassen's algorithm is
more efficient depends on the specific implementation and hardware. Earlier authors had estimated that Strassen's algorithm is
faster for matrices with widths from 32 to 128 for optimized implementations.
[1]
However, it has been observed that this
crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is
often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes
exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or
less).
[2]

You might also like