Volker Strassen (born April 29, 1936) is a German mathematician , a professor emeritus in the department of mathematics and statistics at the University of Konstanz .
40-480: Strassen may refer to: Volker Strassen , mathematician Strassen algorithm Strassen, Luxembourg , town Strassen, Tyrol , town in the district of Lienz in Tyrol, Austria Topics referred to by the same term [REDACTED] This disambiguation page lists articles associated with the title Strassen . If an internal link led you here, you may wish to change
80-549: A × A , u = ( c − a ) × ( C − D ) , v = ( c + d ) × ( C − A ) , w = t + ( c + d − a ) × ( A + D − C ) {\displaystyle t=a{\color {red}\times }A,\;u=(c-a){\color {red}\times }(C-D),\;v=(c+d){\color {red}\times }(C-A),\;w=t+(c+d-a){\color {red}\times }(A+D-C)} . This reduces
120-737: A b c d ] [ A C B D ] = [ t + b × B w + v + ( a + b − c − d ) × D w + u + d × ( B + C − A − D ) w + u + v ] {\displaystyle {\begin{bmatrix}a&b\\c&d\end{bmatrix}}{\begin{bmatrix}A&C\\B&D\end{bmatrix}}={\begin{bmatrix}t+b{\color {red}\times }B&w+v+(a+b-c-d){\color {red}\times }D\\w+u+d{\color {red}\times }(B+C-A-D)&w+u+v\end{bmatrix}}} where t =
160-408: A bilinear map is an important concept in the asymptotic complexity of matrix multiplication. The rank of a bilinear map ϕ : A × B → C {\displaystyle \phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C} } over a field F is defined as (somewhat of an abuse of notation ) In other words, the rank of a bilinear map
200-661: A ring R {\displaystyle {\mathcal {R}}} , for example matrices whose entries are integers or the real numbers. The goal of matrix multiplication is to calculate the matrix product C = A B {\displaystyle C=AB} . The following exposition of the algorithm assumes that all of these matrices have sizes that are powers of two (i.e., A , B , C ∈ Matr 2 n × 2 n ( R ) {\displaystyle A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})} ), but this
240-599: A 1966 presentation at the International Congress of Mathematicians . In 1969, Strassen shifted his research efforts towards the analysis of algorithms with a paper on Gaussian elimination , introducing Strassen's algorithm , the first algorithm for performing matrix multiplication faster than the O( n ) time bound that would result from a naive algorithm. In the same paper he also presented an asymptotically fast algorithm to perform matrix inversion , based on
280-556: A fellow of the American Mathematical Society . Strassen%27s algorithm In linear algebra , the Strassen algorithm , named after Volker Strassen , is an algorithm for matrix multiplication . It is faster than the standard matrix multiplication algorithm for large matrices, with a better asymptotic complexity , although the naive algorithm is often better for smaller matrices. The Strassen algorithm
320-436: 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). A more recent study (2016) observed benefits for matrices as small as 512 and a benefit around 20%. It is possible to reduce the number of matrix additions by instead using the following form discovered by Winograd: [
360-563: A power of 2, then the resulting product will have zero rows and columns just like A {\displaystyle A} and B {\displaystyle B} , and these will then be stripped at this point to obtain the (smaller) matrix C {\displaystyle C} we really wanted. 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
400-420: Is faster: There exists a size N threshold {\displaystyle N_{\text{threshold}}} so that matrices that are larger are more efficiently multiplied with Strassen's algorithm than the "traditional" way. However, the asymptotic statement does not imply that Strassen's algorithm is always faster even for small matrices, and in practice this is in fact not the case: For small matrices,
440-513: Is how many operations exactly one needs for Strassen's algorithms, and how this compares with the standard matrix multiplication that takes approximately 2 N 3 {\displaystyle 2N^{3}} (where N = 2 n {\displaystyle N=2^{n}} ) arithmetic operations, i.e. an asymptotic complexity Θ ( N 3 ) {\displaystyle \Theta (N^{3})} . The number of additions and multiplications required in
SECTION 10
#1732798738434480-434: 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. 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
520-473: Is of no concern for the overall complexity: Adding matrices of size N / 2 {\displaystyle N/2} requires only ( N / 2 ) 2 {\displaystyle (N/2)^{2}} operations whereas multiplication is substantially more expensive (traditionally 2 ( N / 2 ) 3 {\displaystyle 2(N/2)^{3}} addition or multiplication operations). The question then
560-400: Is only conceptually necessary — if the matrices A {\displaystyle A} , B {\displaystyle B} are not of type 2 n × 2 n {\displaystyle 2^{n}\times 2^{n}} , the "missing" rows and columns can be filled with zeros to obtain matrices with sizes of powers of two — though real implementations of
600-548: Is slower than the fastest known algorithms for extremely large matrices, but such galactic algorithms are not useful in practice, as they are much slower for matrices of practical size. For small matrices even faster algorithms exist. Strassen's algorithm works for any ring , such as plus/multiply, but not all semirings , such as min-plus or boolean algebra , where the naive algorithm still works, and so called combinatorial matrix multiplication . Volker Strassen first published this algorithm in 1969 and thereby proved that
640-421: Is the length of its shortest bilinear computation. The existence of Strassen's algorithm shows that the rank of 2 × 2 {\displaystyle 2\times 2} matrix multiplication is no more than seven. To see this, let us express this algorithm (alongside the standard algorithm) as such a bilinear computation. In the case of matrices, the dual spaces A * and B * consist of maps into
680-437: Is typically only used on "large" matrices. This kind of effect is even more pronounced with alternative algorithms such as the one by Coppersmith and Winograd : While asymptotically even faster, the cross-over point N threshold {\displaystyle N_{\text{threshold}}} is so large that the algorithm is not generally used on matrices one encounters in practice. The bilinear complexity or rank of
720-402: The C i j {\displaystyle C_{ij}} in terms of M k {\displaystyle M_{k}} : We recursively iterate this division process until the submatrices degenerate into numbers (elements of the ring R {\displaystyle {\mathcal {R}}} ). If, as mentioned above, the original matrix had a size that was not
760-430: The n 3 {\displaystyle n^{3}} general matrix multiplication algorithm was not optimal. The Strassen algorithm's publication resulted in more research about matrix multiplication that led to both asymptotically lower bounds and improved computational upper bounds. Let A {\displaystyle A} , B {\displaystyle B} be two square matrices over
800-681: The 2 × 2 × 2 {\displaystyle 2\times 2\times 2} matrix multiplication map with itself — an n {\displaystyle n} -th tensor power—is realized by the recursive step in the algorithm shown.) Strassen's algorithm is cache oblivious . Analysis of its cache behavior algorithm has shown it to incur cache misses during its execution, assuming an idealized cache of size M {\displaystyle M} (i.e. with M / b {\displaystyle M/b} lines of length b {\displaystyle b} ). The description above states that
840-568: The University of Göttingen under the supervision of Konrad Jacobs [ de ] . He then took a position in the department of statistics at the University of California, Berkeley while performing his habilitation at the University of Erlangen-Nuremberg , where Jacobs had since moved. In 1968, Strassen moved to the Institute of Applied Mathematics at the University of Zurich , where he remained for twenty years before moving to
SECTION 20
#1732798738434880-839: The analysis of algorithms he has received many awards, including the Cantor medal , the Konrad Zuse Medal , the Paris Kanellakis Award for work on randomized primality testing , the Knuth Prize for "seminal and influential contributions to the design and analysis of efficient algorithms." Strassen was born on April 29, 1936, in Düsseldorf-Gerresheim . After studying music , philosophy, physics, and mathematics at several German universities, he received his Ph.D. in mathematics in 1962 from
920-517: The fast Fourier transform ; see the Schönhage–Strassen algorithm . Strassen is also known for his 1977 work with Robert M. Solovay on the Solovay–Strassen primality test , the first method to show that testing whether a number is prime can be performed in randomized polynomial time and one of the first results to show the power of randomized algorithms more generally. In 1999 Strassen
960-629: The Strassen algorithm can be calculated as follows: let f ( n ) {\displaystyle f(n)} be the number of operations for a 2 n × 2 n {\displaystyle 2^{n}\times 2^{n}} matrix. Then by recursive application of the Strassen algorithm, we see that f ( n ) = 7 f ( n − 1 ) + l 4 n {\displaystyle f(n)=7f(n-1)+l4^{n}} , for some constant l {\displaystyle l} that depends on
1000-628: The University of Konstanz in 1988. He retired in 1998. Strassen began his researches as a probabilist; his 1964 paper An Invariance Principle for the Law of the Iterated Logarithm defined a functional form of the law of the iterated logarithm , showing a form of scale invariance in random walks . This result, now known as Strassen's invariance principle or as Strassen's law of the iterated logarithm , has been highly cited and led to
1040-682: The algorithm do not do this in practice. The Strassen algorithm partitions A {\displaystyle A} , B {\displaystyle B} and C {\displaystyle C} into equally sized block matrices with A i j , B i j , C i j ∈ Mat 2 n − 1 × 2 n − 1 ( R ) {\displaystyle A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R}})} . The naive algorithm would be: This construction does not reduce
1080-675: The constants are known, R / 2 ≤ L ≤ R {\displaystyle R/2\leq L\leq R} . One useful property of the rank is that it is submultiplicative for tensor products , and this enables one to show that 2 n × 2 n × 2 n {\displaystyle 2^{n}\times 2^{n}\times 2^{n}} matrix multiplication can be accomplished with no more than 7 n {\displaystyle 7n} elementary multiplications for any n {\displaystyle n} . (This n {\displaystyle n} -fold tensor product of
1120-402: The cost of the additional additions of matrix blocks outweighs the savings in the number of multiplications. There are also other factors not captured by the analysis above, such as the difference in cost on today's hardware between loading data from memory onto processors vs. the cost of actually doing operations on this data. As a consequence of these sorts of considerations, Strassen's algorithm
1160-588: The elements in the expanded ones. Strassen's algorithm needs to be compared to the "naive" way of doing the matrix multiplication that would require 8 instead of 7 multiplications of sub-blocks. This would then give rise to the complexity one expects from the standard approach: O ( 8 n ) = O ( N log 2 8 ) = O ( N 3 ) {\displaystyle O(8^{n})=O(N^{\log _{2}8})=O(N^{3})} . The comparison of these two algorithms shows that asymptotically , Strassen's algorithm
1200-589: The fairly narrow time savings obtained by using the method in the first place. A good implementation will observe the following: Furthermore, there is no need for the matrices to be square. Non-square matrices can be split in half using the same methods, yielding smaller non-square matrices. If the matrices are sufficiently non-square it will be worthwhile reducing the initial operation to more square products, using simple methods which are essentially O ( n 2 ) {\displaystyle O(n^{2})} , for instance: These techniques will make
1240-432: The fast matrix multiplication algorithm. This result was an important theoretical breakthrough, leading to much additional research on fast matrix multiplication, and despite later theoretical improvements it remains a practical method for multiplication of dense matrices of moderate to large sizes. In 1971 Strassen published another paper together with Arnold Schönhage on asymptotically fast integer multiplication based on
Strassen - Misplaced Pages Continue
1280-495: The field F induced by a scalar double-dot product , (i.e. in this case the sum of all the entries of a Hadamard product .) It can be shown that the total number of elementary multiplications L {\displaystyle L} required for matrix multiplication is tightly asymptotically bound to the rank R {\displaystyle R} , i.e. L = Θ ( R ) {\displaystyle L=\Theta (R)} , or more specifically, since
1320-667: The implementation more complicated, compared to simply padding to a power-of-two square; however, it is a reasonable assumption that anyone undertaking an implementation of Strassen, rather than conventional multiplication, will place a higher priority on computational efficiency than on simplicity of the implementation. In practice, Strassen's algorithm can be implemented to attain better performance than conventional multiplication even for matrices as small as 500 × 500 {\displaystyle 500\times 500} , for matrices that are not at all square, and without requiring workspace beyond buffers that are already needed for
1360-487: The link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=Strassen&oldid=1127442554 " Categories : Disambiguation pages Place name disambiguation pages Disambiguation pages with surname-holder lists Hidden categories: Short description is different from Wikidata All article disambiguation pages All disambiguation pages Volker Strassen For important contributions to
1400-428: The matrices are square, and the size is a power of two, and that padding should be used if needed. This restriction allows the matrices to be split in half, recursively, until limit of scalar multiplication is reached. The restriction simplifies the explanation, and analysis of complexity, but is not actually necessary; and in fact, padding the matrix as described will increase the computation time and can easily eliminate
1440-718: The number of additions performed at each application of the algorithm. Hence f ( n ) = ( 7 + o ( 1 ) ) n {\displaystyle f(n)=(7+o(1))^{n}} , i.e., the asymptotic complexity for multiplying matrices of size N = 2 n {\displaystyle N=2^{n}} using the Strassen algorithm is O ( [ 7 + o ( 1 ) ] n ) = O ( N log 2 7 + o ( 1 ) ) ≈ O ( N 2.8074 ) {\displaystyle O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})} . The reduction in
1480-400: The number of arithmetic operations however comes at the price of a somewhat reduced numerical stability , and the algorithm also requires significantly more memory compared to the naive algorithm. Both initial matrices must have their dimensions expanded to the next power of 2, which results in storing up to four times as many elements, and the seven auxiliary matrices each contain a quarter of
1520-411: The number of matrix additions and subtractions from 18 to 15. The number of matrix multiplications is still 7, and the asymptotic complexity is the same. The outline of the algorithm above showed that one can get away with just 7, instead of the traditional 8, matrix-matrix multiplications for the sub-blocks of the matrix. On the other hand, one has to do additions and subtractions of blocks, though this
1560-458: The number of multiplications: 8 multiplications of matrix blocks are still needed to calculate the C i j {\displaystyle C_{ij}} matrices, the same number of multiplications needed when using standard matrix multiplication. The Strassen algorithm defines instead new values: using only 7 multiplications (one for each M k {\displaystyle M_{k}} ) instead of 8. We may now express
1600-498: Was awarded the Cantor medal , and in 2003 he was co-recipient of the Paris Kanellakis Award with Robert Solovay , Gary Miller , and Michael Rabin for their work on randomized primality testing. In 2008 he was awarded the Knuth Prize for "seminal and influential contributions to the design and analysis of efficient algorithms." In 2011 he won the Konrad Zuse Medal of the Gesellschaft für Informatik . In 2012 he became
#433566