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