2 ms·
There are, but everyone uses variations of the same O(n^3) algorithm taught in college introduction to linear algebra classes because it is numerically stable a
by ryao 2y ago
There are, but everyone uses variations of the same O(n^3) algorithm taught in college introduction to linear algebra classes because it is numerically stable and can be made extremely fast through tweaks that give spatial locality and good cache characteristics. Meanwhile the asymptomatically faster algorithms have such large constants in their big O notation that they are not worth using. FFT based matrix multiplication, which is O((n^2)log(n)), also has numerical instability on top of running slower.
- petters 2y ago> matrix multiplication, which is O((n^2)log(n)) Isn't the fastest theoretical algorithm something like O(n^2.37) ?
- jey 2y agoYes, but it's impractical unless you have galactic-scale matrices to multiply (at least).
- eapriv 2y ago> FFT based matrix multiplication, which is O((n^2)log(n)) What?
- jhanschoo 2y agoFFT is fast Fourier transform, and our best theoretical bounds on multiplication come from methods involving FFT.
- eapriv 2y agoFor matrix multiplication? How?
- ryao 2y agohttps://en.wikipedia.org/wiki/Schönhage–Strassen_algorithm https://en.wikipedia.org/wiki/Schönhage–Strassen_algorithm I forgot the log(log(n)) factor. In any case, for matrix multiplications that people actually do, this algorithm runs slower than a well optimized O(n^3) matrix multiplication implementation because the constant factor in the Big O notation is orders of magnitude larger.
- eapriv 2y agoSchönhage-Strassen is not about matrix multiplication.