39
$\begingroup$

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.807})$ for the multiplication of two $n \times n$ matrices (the exponent is $\frac{\log7}{\log2}$). However, the constant is so large that this algorithm is in fact slower in practice than naive matrix multiplication for small $n$. Similarly, the Coppersmith-Winograd algorithm, which has the lowest asymptotic complexity of all known matrix multiplication algorithms, has an exponent of $2.376$ and was discussed here previously.

Question: Recently, I made a claim in a submitted paper that the Smith normal form algorithm has super-cubical complexity and a reviewer countered by saying that actually, the complexity has been reduced to matrix multiplication time = $n^{2.37\ldots}$. I am not an expert on matrix algorithms and would happily change the offending line, but the experience has forced me to wonder, what are the practical implications of saying "X can be done in matrix multiplication time"? More precisely,

Does there exist an actual software implementation of Coppersmith Winograd? If not, is there a theoretical obstacle to its existence?

By a theoretical obstacle I don't mean something like "Well, it would only be better than existing techniques for $n$ larger than the number of atoms in the universe so what's the point?", but rather something like "the algorithm uses the axiom of choice, or the classification of finite simple groups" etc.

PS: Okay, so there is also this paper which apparently reduces the complexity of the Coppersmith-Winograd approach to $2.3737$ from $2.376$, so I stand corrected about CW being the fastest. The question still stands if we replace CW by the method of V. V. Williams.

$\endgroup$
  • 5
    $\begingroup$ There are software implementations of the Strassen algorithm but am not sure if there is one for Coppersmith Winograd. The problem from an implementation perspective is that the data structure to handle these algorithms gets complex. As far as I know, there is no theoretical obstacle to the existence of such implementations, though I have not completely read the Coppersmith Winograd algorithm. $\endgroup$ – user11000 Jul 6 '12 at 21:03
  • 6
    $\begingroup$ Two points. The exponent for the Stassen algorithm is not exactly $2.8$ but $\log 7/\log2=2.807...$. The constant is not that big, a corse bound being $73.5$. $\endgroup$ – Denis Serre Jul 6 '12 at 21:34
  • 11
    $\begingroup$ I am a bit surprised that in your introduction you make it sound as if Strassen was impractical. Yes, for small n it is not used, but the cross over point are rather moderate (think hundred or so). $\endgroup$ – user9072 Jul 6 '12 at 21:35
  • 3
    $\begingroup$ I am quite surprised that you can compute Smith Normal Form in matrix-multiplication time. Would you happen to have the reference? $\endgroup$ – Igor Rivin Jul 7 '12 at 2:27
  • 5
    $\begingroup$ Igor: I was pointed to this paper by the reviewer: mrzv.org/publications/zzph-mmt/socg11 but I should warn you that I haven't yet had time to go through it and verify the claim $\endgroup$ – Vidit Nanda Jul 7 '12 at 2:55
68
$\begingroup$

There are currently no practical implications of any fast matrix multiplication algorithms besides Strassen's. The Coppersmith/Winograd algorithm and its descendants (Stothers, Williams) are very complex, depend on probabilistic constructions, etc. There's no theoretical obstacle to implementing them in the sense you're asking about, and it's something that's humanly possible, but there's little point to it and I don't believe anyone has ever actually done it. It would be complicated and painful, and the only purpose would be really learning how the algorithm works, since the cross-over point for where it would improve on the naive cubic-time algorithm is enormous (so you'll never actually see any improvement). There are other algorithms that would be somewhat easier to implement, at the cost of worse asymptotic performance, but they are also utterly impractical.

There's also a deeper issue if you try to use algebraic algorithms in practice. The algebraic complexity model typically used for these problems counts only arithmetic operations and considers memory access to be free. This made sense way back when, since a single floating point operation was comparatively expensive, but nowadays memory management can be the real bottleneck in practice. Algebraic complexity is beautiful and theoretically important, but it ignores important practical issues.

If you want to do fast matrix multiplication in practice, it will presumably be on a parallel computer. That introduces further issues of communication complexity; see http://arxiv.org/abs/1202.3173 for an analysis of the Strassen case (both theoretically and in practice).

$\endgroup$
19
$\begingroup$

Recently there is a PhD thesis about the practical fast matrix multiplication algorithms like Strassen:

Matrix multiplication is a core building block for numerous scientific computing and, more recently, machine learning applications. Strassen's algorithm, the original Fast Matrix Multiplication (FMM) algorithm, has long fascinated computer scientists due to its startling property of reducing the number of computations required for multiplying $n \times n$ matrices from $\mathcal{O}(n^3)$ to $\mathcal{O}(n^{2.807})$. Over the last half century, this has fueled many theoretical improvements such as other variations of Strassen-like FMM algorithms. Previous implementations of these FMM algorithms led to the "street wisdom" that they are only practical for large, relatively square matrices, that they require considerable workspace, and that they are difficult to achieve thread-level parallelism. The thesis of this work dispels these notions by demonstrating significant benefits for small and non-square matrices, requiring no workspace beyond what is already incorporated in high-performance implementations of matrix multiplication, and achieving performance benefits on multi-core, many-core, and distributed memory architectures.

This work includes several publications:

Strassen's Algorithm Reloaded. In The International Conference for High Performance Computing, Networking, Storage and Analysis (SC16), Salt Lake City, UT, November 2016.

Generating Families of Practical Fast Matrix Multiplication Algorithms. In 31st IEEE International Parallel and Distributed Processing Symposium (IPDPS17), Orlando, FL, May 29-June 2, 2017.

Strassen's Algorithm for Tensor Contraction. In SIAM Journal on Scientific Computing (SISC), 40(3):C305-C326, 2018.

Implementing Strassen’s Algorithm with CUTLASS on NVIDIA Volta GPUs. FLAME Working Note #88, The University of Texas at Austin, Department of Computer Science. Technical Report TR-18-08. August 23, 2018.

The open source code repositories are here:

https://github.com/flame/fmm-gen

https://github.com/flame/tblis-strassen

Other than that, you might be also interested in this paper:

A framework for practical parallel fast matrix multiplication. In Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2015).

$\endgroup$
  • 2
    $\begingroup$ Thanks, this looks very useful! If I could give another +1 for "Strassen's algorithm reloaded", I would. $\endgroup$ – Vidit Nanda May 12 at 20:17

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.