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

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






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

Search: