Is fast matrix multiplication worth it?

Правка en1, от 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?

Теги matrix multiplication, strassen, matrix

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Dekacc 2016-07-20 20:58:43 921 Initial revision (published)