Fast matrix multiplication does not need to be hard

Revision en2, by i_love_sqrt_decomp, 2025-08-26 05:03:56

I have done a matrix multiplication program that runs ~50x faster than plain naive implementation and ~3x faster than IKJ-order with modular tricks in just 55 lines of code.

Typically, to get this kind of speed (top 4 on Library Checker), you would have to spend 300+ lines of code for a Strassen implementation.

Here is the link: https://judge.yosupo.jp/submission/310249. A lot of the code was based on https://mirror.codeforces.com/blog/entry/101655, aside from the tmp part.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English i_love_sqrt_decomp 2025-08-26 07:48:48 40
en2 English i_love_sqrt_decomp 2025-08-26 05:03:56 27 Tiny change: 'd of speed, you woul' -> 'd of speed (top 4 on Library Checker), you woul'
en1 English i_love_sqrt_decomp 2025-08-26 05:01:46 503 Initial revision (published)