4 ms·

Naive is going to be "that bad" at that size. I tried this on my own system, 4096x4096 matrix multiplication, with the naive algorithm, the naive algorithm wit

Naive is going to be "that bad" at that size. I tried this on my own system, 4096x4096 matrix multiplication, with the naive algorithm, the naive algorithm with swapped loops, and Strassen's algorithm. I had my implementation of Strassen's algorithm switch to the naive algorithm (with bad locality of reference) for 64x64 matrices. The results were 530s for the textbook algorithm, 140s for the textbook algorithm with better cache access, and 94s for Strassen's algorithm.

stephencanon 13y ago
For context, using a hand tuned multithreaded and cache-blocked library implementation of O(n^3) multiplication, a 4096x4096 matrix multiply requires less than two seconds on my current-gen Core i5.
- malingo 13y ago
  You don't always want a multithreaded library implementation though, if the code using the library is already heavily multithreaded.
  - stephencanon 13y ago
    Sure (though it’s worth noting that a correctly-designed high performance library should deliver good performance in that scenario as well; sadly many do not). Single-threaded time on the same system: 5.5 seconds.
- betterunix 13y ago
  The real question is this: how fast would a hand-tuned, multithreaded implementation of Strassen's algorithm be on that system? How fast would Strassen's algorithm be if it used the hand-tuned, multithreaded textbook algorithm for smaller matrices? I am not denying that constant factor improvements are good, all I am saying is that at the sizes the article is talking about Strassen's algorithm is likely to be advantageous. For what it's worth, having my implementation of Strassen's algorithm use the textbook algorithm with better locality of reference reduces the running time to 61 seconds. Improving the running time of the textbook algorithm will also improve the running time of Strassen's algorithm. (Edit: It is also worth mentioning that my implementation of Strassen's algorithm could be sped up with a few basic improvements. For example, right now it requires a lot of calls to malloc/free and it needlessly copies matrices. This is not even remotely production-grade software, it was just hastily thrown together.)

stephencanon 13y ago

For context, using a hand tuned multithreaded and cache-blocked library implementation of O(n^3) multiplication, a 4096x4096 matrix multiply requires less than two seconds on my current-gen Core i5.

malingo 13y ago
You don't always want a multithreaded library implementation though, if the code using the library is already heavily multithreaded.
- stephencanon 13y ago
  Sure (though it’s worth noting that a correctly-designed high performance library should deliver good performance in that scenario as well; sadly many do not). Single-threaded time on the same system: 5.5 seconds.
betterunix 13y ago
The real question is this: how fast would a hand-tuned, multithreaded implementation of Strassen's algorithm be on that system? How fast would Strassen's algorithm be if it used the hand-tuned, multithreaded textbook algorithm for smaller matrices? I am not denying that constant factor improvements are good, all I am saying is that at the sizes the article is talking about Strassen's algorithm is likely to be advantageous. For what it's worth, having my implementation of Strassen's algorithm use the textbook algorithm with better locality of reference reduces the running time to 61 seconds. Improving the running time of the textbook algorithm will also improve the running time of Strassen's algorithm. (Edit: It is also worth mentioning that my implementation of Strassen's algorithm could be sped up with a few basic improvements. For example, right now it requires a lot of calls to malloc/free and it needlessly copies matrices. This is not even remotely production-grade software, it was just hastily thrown together.)