The trivial: O(n^3)
The Strassen: O(n^2.807)
The fastest*: O(n^2.376)
As the Strassen algorithm [ http://0rz.tw/bf2Xo ] mentioned:
The reduction in the number of multiplications however comes at the price of a somewhat reduced numeric stability.
* Coppersmith–Winograd algorithm
Reference:
*The Simultaneous Triple Product Property and Group-theoretic Results for the Exponent of Matrix Multiplication, arXiv:cs.CS/0703145
沒有留言:
張貼留言