> Fastest known matrix multiplication algorithm... ...for general matrices. Four... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		Rayhem on Jan 17, 2022 \| parent \| context \| favorite \| on: Matrix Multiplication > 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

amelius on Jan 17, 2022 [–]

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

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact