8

Strassen’s Matrix Multiplication algorithm has theoretical performance of $ O( n^{log_2 7}) $. Regular MM algorithm has performance of $ O( n^{3}) $.

At certain sizes of matrices (lets call it $n*n$), Regular MM works better. However, once size $n*n$ is breached, Strassen’s MM works better.

Question: at what size of the matrix, Strassen’s MM algorithm works better ?
Thanks !

newprint
  • 231
  • 2
  • 3

3 Answers3

6

Others have commented on the machine dependence of it. What I'd like to point out is that Strassen's algorithm only concerns dense matrices and that the matrices need to be fairly large for it to be worthwhile. However, this is a case one doesn't encounter all that often in applications:

  • If your matrix really is dense and large, then you probably have all sorts of other problems as well. For example, you are probably not just multiplying it but you want to compute principle components, eigenvalues, inverses, etc. Accelerating the matrix vector product might help you but there are multiple other layers of algorithms that will prove to be a bottleneck to the size of the problems you can solve that you will hit before matrix products become important.

  • Matrix-matrix products aren't that common to begin with. Most of the time we consider a matrix a linear operator on vector spaces and so when we see the product of two matrices we think of it is one operator applied to a vector and then another operator applied to the result. Reflecting this in software is almost always the more efficient way compared to actually multiplying out the operators.

  • Very large problems are often formulated in terms of sparse matrices for which Strassen's algorithm does not apply. This is certainly true for everything that comes from partial differential equations (including boundary integral equations) but also for things like most graph based algorithms (e.g. social graphs, which are also sparse).

Wolfgang Bangerth
  • 55,373
  • 59
  • 119
  • The conventional wisdom is boundary element methods result in dense matrices, though fewer unknowns than FEM due to discretizing the boundary but not an interior region. – hardmath Nov 14 '12 at 03:35
  • That's the naive way of doing it. All practically relevant approaches sparsify the matrix one way or another, either by using the fact that the Green's function is global but has decay properties, or by using something like a Fast Multipole Method. The boundary element method is not competitive when you work with dense matrices. – Wolfgang Bangerth Nov 15 '12 at 03:21
  • @WolfgangBangerth: Consider a FEM discretization of a 3D problem which uses a 1000 x 1000 x 1000 mesh, which might result in a billion degrees of freedom. If a multifrontal method is used, then the root separator will likely involve a 1000 x 1000 plane, which will involve about a million degrees of freedom, which produces a million x million dense matrix. If the Green's function is not particularly well behaved, there are few options other than to directly factor this large dense matrix, and one potential approach is to use Strassen's algorithm. – Jack Poulson Dec 26 '12 at 22:43
  • That seems about right. That might be one reason why people don't do direct factorizations of $10^9$ matrices... – Wolfgang Bangerth Dec 28 '12 at 18:22
  • "Matrix-matrix products aren't that common to begin with. " -- this point is pretty strong and interesting. Do you have references for more details please? – AJed Aug 05 '16 at 20:11
  • 1
    @AJed -- fair question. My view may be tainted by my background in PDEs. Matrix-matrix products are certainly common in computational chemistry/molecular dynamics, for example. – Wolfgang Bangerth Aug 06 '16 at 03:36
4

For a relatively recent (2010) benchmarking study of Strassen vs. conventional matrix multiplication, see:

http://www.ics.uci.edu/~fastmm/FMM-Reference/paoloA.ishp-vi.pdf

The basic conclusions are that the the point at which it becomes worthwhile to use Strassen's algorithm depends on the machine and that in no case were the authors able to get significant (the best improvement was only 15%) performance improvements by using Strassen's algorithm for matrices of reasonable size.

Brian Borchers
  • 18,719
  • 1
  • 39
  • 70
  • 1
    Is that really a recent comparison? The machines they report on have between 100MHz and 2GHz. It's been many years since these machines were current... – Wolfgang Bangerth Nov 13 '12 at 02:31
  • I wrote "relatively recent"- the paper was written in 2010, and many of the machines described in the paper were a few years old then. However, the general trend in recent years has been consistently in the direction of less memory bandwidth and higher latency relative to to the speed of the floating point processors and more dependence on caching. These factors all tend to make conventional blocked matrix multiplication methods faster than Strassen's algorithm in practice. I haven't yet seen a convincing demonstration that Strassen's algorithm can be substantially faster in practice. – Brian Borchers Nov 28 '12 at 05:03
2

The crossover point is highly dependent on the particular machine and architecture. For modern linear algebra libraries, the largest impact on performance is the cache hierarchy within CPUs, and so therefore it depends on how you structure and order the operations for either method. This aside, there are also accuracy issues, as I recall, Strassen's algorithm produces larger errors.

Victor Liu
  • 4,480
  • 18
  • 28
  • I don't think it produces any "errors" at all, it just splits the matrix into smaller blocks, and then recombines them. – newprint Nov 12 '12 at 03:29
  • 1
    What Victor Liu is referring to is the rounding error behavior of Strassen's algorithm. One has rounding error even in conventional row-column matrix multiplication, unless matrix entries are exact, e.g. integers of reasonably small size. – hardmath Nov 12 '12 at 15:07