2007-08-20

Algorithm for square matrix multiplication

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

沒有留言: