3 ms·
> FFT based matrix multiplication, which is O((n^2)log(n)) What?
by 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.