Strassen algorithm

Strassen algorithm

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, and is useful in practice for large matrices.

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 of Shmuel Winograd in 1980Dubious|Which Winograd algorithm? (which uses 7 binary multiplications, but 15 binary additions instead of 18 with the Strassen algorithm), and the more complex Coppersmith–Winograd algorithm published in 1987.

Algorithm

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

:mathbf{C} = mathbf{A} mathbf{B} qquad mathbf{A},mathbf{B},mathbf{C} in R^{2^n imes 2^n}

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: mathbf{A} =egin{bmatrix}mathbf{A}_{1,1} & mathbf{A}_{1,2} \mathbf{A}_{2,1} & mathbf{A}_{2,2}end{bmatrix}mbox { , }mathbf{B} =egin{bmatrix}mathbf{B}_{1,1} & mathbf{B}_{1,2} \mathbf{B}_{2,1} & mathbf{B}_{2,2}end{bmatrix}mbox { , }mathbf{C} =egin{bmatrix}mathbf{C}_{1,1} & mathbf{C}_{1,2} \mathbf{C}_{2,1} & mathbf{C}_{2,2}end{bmatrix}

with

:mathbf{A}_{i,j}, mathbf{B}_{i,j}, mathbf{C}_{i,j} in R^{2^{n-1} imes 2^{n-1

then

:mathbf{C}_{1,1} = mathbf{A}_{1,1} mathbf{B}_{1,1} + mathbf{A}_{1,2} mathbf{B}_{2,1} :mathbf{C}_{1,2} = mathbf{A}_{1,1} mathbf{B}_{1,2} + mathbf{A}_{1,2} mathbf{B}_{2,2} :mathbf{C}_{2,1} = mathbf{A}_{2,1} mathbf{B}_{1,1} + mathbf{A}_{2,2} mathbf{B}_{2,1} :mathbf{C}_{2,2} = mathbf{A}_{2,1} mathbf{B}_{1,2} + mathbf{A}_{2,2} mathbf{B}_{2,2}

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

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

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

:mathbf{C}_{1,1} = mathbf{M}_{1} + mathbf{M}_{4} - mathbf{M}_{5} + mathbf{M}_{7}:mathbf{C}_{1,2} = mathbf{M}_{3} + mathbf{M}_{5}:mathbf{C}_{2,1} = mathbf{M}_{2} + mathbf{M}_{4}:mathbf{C}_{2,2} = mathbf{M}_{1} - mathbf{M}_{2} + mathbf{M}_{3} + mathbf{M}_{6}

We iterate this division process "n"-times until the submatrices degenerate into numbers (group elements).

Practical implementations of Strassen's algorithm switch to standard methods of matrix multiplication for small enough submatrices, for which they are more efficient. The particular crossover point for which Strassen's algorithm is more efficient depends on the specific implementation and hardware. It has been estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations, [ [http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK3/NODE138.HTM Matrix Multiplication notes] ] and 60,000 or more for basic implementations. [ [http://www.stanford.edu/~boyko/pubs/MatrixMult_SURJ_2004.pdf Ultra-Fast Matrix Multiplication] ]

Numerical analysis

The standard matrix multiplications takes :n^3 = n^{log_{2}8}multiplications of the elements in the ring "R". We ignore the additions needed because, depending on "R", 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:n^{log_{2}7}approx n^{2.807}.

The reduction in the number of multiplications however comes at the price of a somewhat reduced numerical stability.

See also

* Z-order matrix representation

References

* Strassen, Volker, "Gaussian Elimination is not Optimal", Numer. Math. 13, p. 354-356, 1969
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 28: Section 28.2: Strassen's algorithm for matrix multiplication, pp.735–741.

External links

*MathWorld|urlname=StrassenFormulas|title=Strassen's Formulas (also includes formulas for fast matrix inversion)


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Schönhage-Strassen algorithm — The Schönhage Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971. [A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen ,… …   Wikipedia

  • Strassen — can refer to: * the mathematician Volker Strassen * the Strassen algorithm * the town Strassen, Luxembourg *Strassen, Austria, a town in the district of Lienz in TyrolSee also: *Straße …   Wikipedia

  • Strassen-Algorithmus — Der Strassen Algorithmus (benannt nach dem deutschen Mathematiker Volker Strassen) ist ein Algorithmus aus der Linearen Algebra und wird zur Matrizenmultiplikation verwendet. Der Strassen Algorithmus realisiert die Matrizenmultiplikation… …   Deutsch Wikipedia

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

  • Volker Strassen — is a German mathematician. He received in 2003, with three others, the Paris Kanellakis Award of the ACM, for the Solovay Strassen primality test.In 1971 Strassen published a paper together with Arnold Schönhage on asymptotically fastinteger… …   Wikipedia

  • Fürer's algorithm — is an integer multiplication algorithm for very large numbers possessing a very low asymptotic complexity. It was created in 2007 by Martin Fürer of Pennsylvania State UniversityFuhrer, M. (2007). Faster Integer Multiplication in Proceedings of… …   Wikipedia

  • Solovay–Strassen primality test — The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen, is a probabilistic test to determine if a number is composite or probably prime. It has been largely superseded by the Miller–Rabin primality test, but has… …   Wikipedia

  • Monte Carlo algorithm — In computing, a Monte Carlo algorithm is a randomized algorithm whose running time is deterministic, but whose output may be incorrect with a certain (typically small) probability. The related class of Las Vegas algorithms is also randomized, but …   Wikipedia

  • Cipolla's algorithm — In computational number theory, Cipolla s algorithm is a technique for solving a congruence of the form x2 = n, where , so n is the square of x, and where p is an odd prime. Here denotes the finite field with p elements; . Th …   Wikipedia

  • Williams' p + 1 algorithm — In computational number theory, Williams p + 1 algorithm is an integer factorization algorithm, one of the family of algebraic group factorisation algorithms. It was invented by Hugh C. Williams in 1982. It works well if the number N to be… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”