6 ms·
> Fastest known matrix multiplication algorithm... ...for general matrices. Fourier transforms do indeed diagonalize circulant matrices[1], making their multip
by Rayhem 5y ago
> Fastest known matrix multiplication algorithm...
...for general matrices. Fourier transforms do indeed diagonalize circulant matrices[1], making their multiplications O(2 n log n + n) -> O(n log n).
[1]: https://en.wikipedia.org/wiki/Circulant_matrix https://en.wikipedia.org/wiki/Circulant_matrix
- amelius 5y agoYes, no doubt that there are faster algorithms for specific matrices. That matrix you are bringing into the discussion is only n-dimensional, so not surprising that you can multiply it faster than a matrix that is n×n dimensional.