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.
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.
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)
> 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?
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).
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?
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.
