Coppersmith–Winograd approaches take the crown for asymptotic scaling in matrix-matrix multiplication [1].
It kind of blows my mind that a tight bound on the complexity of matrix-matrix multiplication still isn't known!
Edit: Some quick googling shows that François Le Gall took the crown in 2014.
[1] https://en.wikipedia.org/wiki/Computational_complexity_of_ma...
E.g. strassens-algorithms assumes something like:
(A+B)C - BC = AC
With the convential floating point representation this becomes a problem if B >> A because of rounding errors.
Most algorithms faster than Strassen assume:
(( fA + B)C - BC)/f = AC
and
(fA + B)C = BC +fAC
f is then choosen in such a way, that fAC is neglegible. But if that is the case fA is much smaller than B and we automatically get numerical problems.
There is a procedure to remove the fAC terms (which would imply that f could be choosen close to 1) which armortizes over enough recursions. But for Coppersmith-Winograd (and derivatives like Le-Galls algorithm). We need to divide the matrix in each recursion step into enough submatrices that the indices can be treated heuristically(lets say a division of each index in each iteration in 100 subindices). This would imply the sides of each matrix must be at least of size 100^n_recusion. We won't need to multiply matrices of that size.
If modern train engine produced 700 times as much power that’s only 26 times faster for the same cargo (don’t they pull more now?) And we do have trains that can go 260 km/hr... just not with cargo.
progress, man.