4
$\begingroup$

I have been reading about the Strassen Algorithm for matrix multiplication.

As mentioned in Introduction to Algorithms by Cormen , the algorithm is not intuitive. However I am curious to know if there exists any rigorous mathematical proof of the algorithm and what actually went into the design of the algorithm.

I tried searching on Google and stackoverflow, but all links are only on comparing Strassen's approach to standard matrix multiplication approach or they elaborate on the procedure presented by the algorithm.

Note: The same question has been asked on https://stackoverflow.com/questions/19229454/strassens-algorithm-proof , but without any definite answers

$\endgroup$
  • 3
    $\begingroup$ Check out this question on CSTheory. $\endgroup$ – Juho Oct 8 '13 at 12:12
5
$\begingroup$

The main idea of the algorithm is to find a way to multiply two $n\times n$ matrices with less than $n^3$ "essential" multiplications (multiplications of two elements of the matrices). This forms part of a larger theory, algebraic complexity theory. Here are a few highlights:

  1. Every algorithm for multiplying two matrices can be formulated (at a small loss) as a bilinear algorithm: you form some linear combinations $\alpha_1,\ldots,\alpha_k$ of entries of the first matrix, some linear combinations $\beta_1,\ldots,\beta_k$ of entries of the second matrix, compute $\gamma_i = \alpha_i \beta_i$, and then every entry of the product matrix is a linear combination of the $\gamma_i$.

  2. This can be formulated as computing the tensor rank of the matrix multiplication tensor $\langle n,n,n \rangle = \sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n x_{ij} y_{jk} z_{ik}$. The tensor rank is similar to the more familiar matrix rank, and corresponds to the number of "essential" multiplications ($k$ in the preceding example).

  3. Any non-trivial bound on $\langle n,n,n \rangle$ for any $n$ translates to a non-trivial matrix multiplication algorithm for all $n$, via the same recursive approach as Strassen's algorithm (this approach is also known as tensorization). There are several extensions, culminating in Schönhage's asymptotic sum inequality.

  4. The asymptotic sum inequality can handle identities involving disjoint sums of matrix tensors (in plain English, ways of multiplying several matrices at once using fewer "essential" multiplications than the trivial algorithm uses), and can even handle "approximate" identities (border rank). Strassen came up with another method (the laser method) that can handle non-disjoint sums, and this led to the Coppersmith-Winograd algorithm and its descendants, which is where things stand today.

$\endgroup$
  • $\begingroup$ You say that Coppersmith-Winograd algorithm can handle non-disjoint sums. In their algorithm they speak about products of disjoint matrix products. Are the $n^{2.376}$ multiplications independants ? In other words, can these $n^{2.376}$ multiplications be computed at the same time, as the Strassen one ? Thank you $\endgroup$ – user7060 Jul 2 '15 at 7:49
  • $\begingroup$ No, the Coppersmith–Winograd algorithm only works for multiplying two square matrices. Its design uses as a component the asymptotic sum inequality, which handles non-disjoint sums occurring during the design phase. The scalar multiplications generated by the algorithm can all be computed in parallel, and this is true for all matrix multiplication algorithms. That's a consequence of Strassen's normal form theorem. $\endgroup$ – Yuval Filmus Jul 2 '15 at 12:09
  • $\begingroup$ Thank you very much. Why are you talking about scalar multiplications ? This is not bilinear multiplications ? $\endgroup$ – user7060 Jul 2 '15 at 12:13
  • $\begingroup$ They're multiplication of two linear combinations of matrix entries, so in the end you're multiplying two scalar quantities. You can call this operation whatever you want. $\endgroup$ – Yuval Filmus Jul 2 '15 at 12:15
  • $\begingroup$ Thanks. Can the Strassen's normal form theorem be applied for any matrix product algorithm ? I don't know this theorem. $\endgroup$ – user7060 Jul 2 '15 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.