News for hackers. Stuff that matters.
Re:Performance experiments with matrix multiplication in Rust by electricslpnsld on Sunday May 13, 2018 @08:05PM (#17061762)
> Strassen's algorithm is asymptotically the fastest known algorithm for dense matrix multiplication

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

Re:Performance experiments with matrix multiplication in Rust by Paul_Diraq on Monday May 14, 2018 @01:48AM (#17063004)
The problem with the algorithms faster than conventional mm is, that they are defined on mathematical numbers.

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.

Re:Performance experiments with matrix multiplication in Rust by geezerjay on Monday May 14, 2018 @02:32PM (#17068132)
Thank you for posting your comment. Very insightful and packed with goodies!
Re:Performance experiments with matrix multiplication in Rust by gh02t on Tuesday May 15, 2018 @05:02PM (#17077835)
Oh, right indeed. I had forgotten about those since they aren't really practical. I honestly find it pretty amazing that any sub-cubic algorithms can even exist for dense matrix multiplication. It's just far enough away from my expertise to seem magical.