Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Is fast matrix multiplication worth it?

Revision en1, by Dekacc, 2016-07-20 20:58:43

Recently I've been reading about matrix multiplication algorithms, more specifically Strassen's algorithm for fast matrix multiplication that runs in O(n^2.81) time as opposed to the standard O(n^3) time for the naive approach. But this speed up comes at a cost, for example we need to pad the matrix with zeroes if n isn't a power of 2, and even though it is asymptotically faster, it also carries a bigger constant factor since it does more additions. Also, it is more memory intensive, and it certainly is harder to implement correctly and optimally.

So my question is: Is the time complexity improvement worth all of these drawbacks in a competitive setting? Are there any problems that are unsolvable with standard matrix multiplication, but are solvable with fast matrix multiplication? And what method do all the best competitors use when they need to multiply 2 matrices?

Tags matrix multiplication, strassen, matrix

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Dekacc 2016-07-20 20:58:43 921 Initial revision (published)