4 ms·

I actually find the practicalities of algorithm choice even more fascinating. For example, Strassen's algorithm is asymptotically the fastest known algorithm fo

by gh02t 8y ago

I actually find the practicalities of algorithm choice even more fascinating. For example, Strassen's algorithm is asymptotically the fastest known algorithm for dense matrix multiplication in certain situations (medium sized matrices), but it is rarely used because it is complicated to implement and less numerically stable.

electricslpnsld 8y ago
> 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_mathematical_operations#Matrix_algebra https://en.wikipedia.org/wiki/Computational_complexity_of_ma...
- Paul_Diraq 8y ago
  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.
  - geezerjay 8y ago
    Thank you for posting your comment. Very insightful and packed with goodies!
- gh02t 8y ago
  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.

by gh02t 8y ago

electricslpnsld 8y ago

> 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_mathematical_operations#Matrix_algebra https://en.wikipedia.org/wiki/Computational_complexity_of_ma...

Paul_Diraq 8y ago
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.
- geezerjay 8y ago
  Thank you for posting your comment. Very insightful and packed with goodies!
gh02t 8y ago
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.