News for hackers. Stuff that matters.
Re:Show HN: Matrix Multiplication with Half the Multiplications by abetusk on Friday March 15, 2024 @01:09PM (#39718054)
I don't know why this answer is getting downvoted. This is absolutely correct.

W. Miller has a paper discussing, under conditions of numerical stability, O(n^3) multiplications is necessary [0]. Any algorithm that gets sub cubic runtime for matrix multiplication, like Strassen's or Coppersmith's, must sacrifice some amount of precision or stability.

[0] https://epubs.siam.org/doi/10.1137/0204009

Re:Show HN: Matrix Multiplication with Half the Multiplications by gyrovagueGeist on Friday March 15, 2024 @01:57PM (#39718700)