3 ms·

The article presents a note on the 6 well known matrix compositions. He states that all of them have cubic complexity, but practical algorithms with better expo

The article presents a note on the 6 well known matrix compositions. He states that all of them have cubic complexity, but practical algorithms with better exponents exist for all of them.

adgjlsfhk1 4y ago
They're all basically O(M(n)) where M(n) is your matrix multiplication time. Even though M(n)<=n^2.3...., it's reasonable to say that it's n^3, because in practice, no one uses the sub-cubic algorithms. Strassen is possibly workable, but it isn't widely used, and all of the sub-cubic algorithms have accuracy tradeoffs.
photon-torpedo 4y ago
> but practical algorithms with better exponents exist for all of them. I'm aware of randomized algorithms with better complexity, which come at the cost of only giving approximate results (though the approximation may be perfectly good for practical purposes). See e.g. [1]. Are there other approaches? [1] https://doi.org/10.1137/090771806 https://doi.org/10.1137/090771806
- owlbite 4y ago
  If the data is Sparse (which is not uncommon for large matrices in the real world), you can exploit the sparsity to do significantly better then O(n**3).
oh_my_goodness 4y ago
Could you link a practical algorithm with an exponent lower than 3? (I think of these things https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication https://en.wikipedia.org/wiki/Computational_complexity_of_ma... as not being practical, but I'd love to be wrong. )
- daniel-cussen 4y ago
  https://www.fgemm.com https://www.fgemm.com, coming soon.
- gnufx 4y ago
  For something Strassen-ish you could look at https://jianyuhuang.com/papers/sc16.pdf https://jianyuhuang.com/papers/sc16.pdf and the GPU implementation https://apps.cs.utexas.edu/apps/sites/default/files/tech_reports/GPUStrassen.pdf https://apps.cs.utexas.edu/apps/sites/default/files/tech_rep...
  - FabHK 4y ago
    That's matrix-matrix multiplication. Nobody disputes that Strassen etc. have sub-cubic complexity. What about one of the six decompositions mentioned, as GP claimed?
    - gnufx 4y ago
      I responded to a post about the practicality of MM multiplication methods, though GEMM is quite fundamental.
martinhath 4y ago
The fact that they're all cubic isn't really the notable part of the runtime of computing the different decompositions, because the constants involved are really different. In practice, a common reason for computing many of these decompositions is to solve a linear system `Ax=b`, because with the decomposition in hand it is really easy to solve the whole system (using e.g. backsubstitution). For instance, with C++s Eigen, look at the 100x100 column of [1], and we can see that there's orders of magnitude difference between the fast and slow approaches. THey're all still cubic, sure, but we're talking 168x difference here. (of course, it's not so clear cut, since robustness varies, not all methods are applicable, and the benchmark is for solving the system, not computing the decomposition, but overall, knowledge of which decomposition is fast and which is not is absolutely crucial to practitioners) [1]: https://eigen.tuxfamily.org/dox/group__DenseDecompositionBenchmark.html https://eigen.tuxfamily.org/dox/group__DenseDecompositionBen...
FabHK 4y ago
Can you provide a source? For example, the SVD (Golub-Kahan-Reinsch) method generally involves bidiagonalisation of the matrix and then implicit QR steps, which are often achieved with Householder reflections and Givens rotations. Sure, all of those are conceptually matrix multiplications, but they're not implemented as O(N^3) matrix multiplications; rather, their special structure is exploited so that they're faster. Yet, the entire algorithm is still cubic. So not sure Strassen would accelerate things.

The article presents a note on the 6 well known matrix compositions. He states that all of them have cubic complexity, but practical algorithms with better exponents exist for all of them.

adgjlsfhk1 4y ago

They're all basically O(M(n)) where M(n) is your matrix multiplication time. Even though M(n)<=n^2.3...., it's reasonable to say that it's n^3, because in practice, no one uses the sub-cubic algorithms. Strassen is possibly workable, but it isn't widely used, and all of the sub-cubic algorithms have accuracy tradeoffs.

photon-torpedo 4y ago

> but practical algorithms with better exponents exist for all of them. I'm aware of randomized algorithms with better complexity, which come at the cost of only giving approximate results (though the approximation may be perfectly good for practical purposes). See e.g. [1]. Are there other approaches? [1] https://doi.org/10.1137/090771806 https://doi.org/10.1137/090771806

owlbite 4y ago
If the data is Sparse (which is not uncommon for large matrices in the real world), you can exploit the sparsity to do significantly better then O(n**3).

oh_my_goodness 4y ago

Could you link a practical algorithm with an exponent lower than 3? (I think of these things https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication https://en.wikipedia.org/wiki/Computational_complexity_of_ma... as not being practical, but I'd love to be wrong. )

daniel-cussen 4y ago
https://www.fgemm.com https://www.fgemm.com, coming soon.
gnufx 4y ago
For something Strassen-ish you could look at https://jianyuhuang.com/papers/sc16.pdf https://jianyuhuang.com/papers/sc16.pdf and the GPU implementation https://apps.cs.utexas.edu/apps/sites/default/files/tech_reports/GPUStrassen.pdf https://apps.cs.utexas.edu/apps/sites/default/files/tech_rep...
- FabHK 4y ago
  That's matrix-matrix multiplication. Nobody disputes that Strassen etc. have sub-cubic complexity. What about one of the six decompositions mentioned, as GP claimed?
  - gnufx 4y ago
    I responded to a post about the practicality of MM multiplication methods, though GEMM is quite fundamental.

martinhath 4y ago

The fact that they're all cubic isn't really the notable part of the runtime of computing the different decompositions, because the constants involved are really different. In practice, a common reason for computing many of these decompositions is to solve a linear system `Ax=b`, because with the decomposition in hand it is really easy to solve the whole system (using e.g. backsubstitution). For instance, with C++s Eigen, look at the 100x100 column of [1], and we can see that there's orders of magnitude difference between the fast and slow approaches. THey're all still cubic, sure, but we're talking 168x difference here. (of course, it's not so clear cut, since robustness varies, not all methods are applicable, and the benchmark is for solving the system, not computing the decomposition, but overall, knowledge of which decomposition is fast and which is not is absolutely crucial to practitioners) [1]: https://eigen.tuxfamily.org/dox/group__DenseDecompositionBenchmark.html https://eigen.tuxfamily.org/dox/group__DenseDecompositionBen...

FabHK 4y ago

Can you provide a source? For example, the SVD (Golub-Kahan-Reinsch) method generally involves bidiagonalisation of the matrix and then implicit QR steps, which are often achieved with Householder reflections and Givens rotations. Sure, all of those are conceptually matrix multiplications, but they're not implemented as O(N^3) matrix multiplications; rather, their special structure is exploited so that they're faster. Yet, the entire algorithm is still cubic. So not sure Strassen would accelerate things.