Strassen algorithm

From Free net encyclopedia

In the mathematical discipline of linear algebra, the Strassen algorithm, named after Volker Strassen, is an algorithm used for matrix multiplication. It is asymptotically faster than the standard matrix multiplication algorithm, but slower than the fastest known algorithm.

Contents

[edit]

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 Gaussian elimination is not optimal. His paper started the search for even faster algorithms such as the Coppersmith-Winograd algorithm.

[edit]

Algorithm

Let A, B be two square matrices over a field F. We want to calculate the matrix product C as

<math>\mathbf{C} = \mathbf{A} \mathbf{B} \qquad \mathbf{A},\mathbf{B},\mathbf{C} \in F^{2^n \times 2^n}</math>

If the matrices A, B are not of type 2n x 2n we fill the missing rows and columns with zeros.

We partition A, B and C into equally sized block matrices

<math>

\mathbf{A} = \begin{bmatrix} \mathbf{A}_{1,1} & \mathbf{A}_{1,2} \\ \mathbf{A}_{2,1} & \mathbf{A}_{2,2} \end{bmatrix} \mbox { , } \mathbf{B} = \begin{bmatrix} \mathbf{B}_{1,1} & \mathbf{B}_{1,2} \\ \mathbf{B}_{2,1} & \mathbf{B}_{2,2} \end{bmatrix} \mbox { , } \mathbf{C} = \begin{bmatrix} \mathbf{C}_{1,1} & \mathbf{C}_{1,2} \\ \mathbf{C}_{2,1} & \mathbf{C}_{2,2} \end{bmatrix} </math>

with

<math>\mathbf{A}_{i,j}, \mathbf{B}_{i,j}, \mathbf{C}_{i,j} \in F^{2^{n-1} \times 2^{n-1}}</math>

then

<math>\mathbf{C}_{1,1} = \mathbf{A}_{1,1} \mathbf{B}_{1,1} + \mathbf{A}_{1,2} \mathbf{B}_{2,1} </math>
<math>\mathbf{C}_{1,2} = \mathbf{A}_{1,1} \mathbf{B}_{1,2} + \mathbf{A}_{1,2} \mathbf{B}_{2,2} </math>
<math>\mathbf{C}_{2,1} = \mathbf{A}_{2,1} \mathbf{B}_{1,1} + \mathbf{A}_{2,2} \mathbf{B}_{2,1} </math>
<math>\mathbf{C}_{2,2} = \mathbf{A}_{2,1} \mathbf{B}_{1,2} + \mathbf{A}_{2,2} \mathbf{B}_{2,2} </math>

With this construction we have not reduced the number of multiplications. We still need 8 multiplications to calculate the Ci,j matrices, the same number of multiplications we need when using standard matrix multiplication.

Now comes the important part. We define new matrices

<math>\mathbf{M}_{1} := (\mathbf{A}_{1,1} + \mathbf{A}_{2,2}) (\mathbf{B}_{1,1} + \mathbf{B}_{2,2})</math>
<math>\mathbf{M}_{2} := (\mathbf{A}_{2,1} + \mathbf{A}_{2,2}) \mathbf{B}_{1,1}</math>
<math>\mathbf{M}_{3} := \mathbf{A}_{1,1} (\mathbf{B}_{1,2} - \mathbf{B}_{2,2})</math>
<math>\mathbf{M}_{4} := \mathbf{A}_{2,2} (\mathbf{B}_{2,1} - \mathbf{B}_{1,1})</math>
<math>\mathbf{M}_{5} := (\mathbf{A}_{1,1} + \mathbf{A}_{1,2}) \mathbf{B}_{2,2}</math>
<math>\mathbf{M}_{6} := (\mathbf{A}_{2,1} - \mathbf{A}_{1,1}) (\mathbf{B}_{1,1} + \mathbf{B}_{1,2})</math>
<math>\mathbf{M}_{7} := (\mathbf{A}_{1,2} - \mathbf{A}_{2,2}) (\mathbf{B}_{2,1} + \mathbf{B}_{2,2})</math>

which are then used to express the Ci,j in terms of Mk. Because of our definition of the Mk we can eliminate one matrix multiplication and reduce the number of multiplications to 7 (one multiplications for each Mk) and express the Ci,j as

<math>\mathbf{C}_{1,1} = \mathbf{M}_{1} + \mathbf{M}_{4} - \mathbf{M}_{5} + \mathbf{M}_{7}</math>
<math>\mathbf{C}_{1,2} = \mathbf{M}_{3} + \mathbf{M}_{5}</math>
<math>\mathbf{C}_{2,1} = \mathbf{M}_{2} + \mathbf{M}_{4}</math>
<math>\mathbf{C}_{2,2} = \mathbf{M}_{1} - \mathbf{M}_{2} + \mathbf{M}_{3} + \mathbf{M}_{6}</math>

We iterate this division process n-times until the submatrices degenerate into numbers.

Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which they are more efficient; the overhead of Strassen's algorithm implies that these "small enough" submatrices are actually quite large, well into thousands of elements.

[edit]

Numerical analysis

The standard matrix multiplications takes

<math>n^3 = n^{\log_{2}8}</math>

multiplications of the elements in the field F. We ignore the additions needed because, depending on F, they can be much faster than the multiplications in computer implementations, especially if the sizes of the matrix entries exceed the word size of the machine.

With the Strassen algorithm we can reduce the number of multiplications to

<math>n^{\log_{2}7}\approx n^{2.807}</math>.

Unfortunately, Strassen's algorithm is not numerically well-behaved. It is only weakly stable, i.e., the computed result C of the product AB satisfies the inequality

<math> ||\mathbf{C}-\mathbf{AB}|| \le n u ||\mathbf{A}|| \, ||\mathbf{B}|| + O(u^2)</math>

where u is the unit roundoff error, while the corresponding strong stability inequality (obtained by replacing matrix norms with absolute values of the matrix elements) does not hold.

[edit]

External links

[edit]

References

ja:Strassenのアルゴリズム

Retrieved from "http://www.netipedia.com/index.php/Strassen_algorithm"