4 ms·

"For the right sized matrix, one is bound by compute speed and one by memory access." I am not sure that is a distinction worth making. Memory access and comp

"For the right sized matrix, one is bound by compute speed and one by memory access." I am not sure that is a distinction worth making. Memory access and computation go hand-in-hand: programs do not access memory without performing some computation, and computations cannot be performed without accessing some kind of memory (even if it is just a register). At scale an asymptotically faster algorithm will perform fewer computations and fewer memory accesses (for all levels of memory) than an asymptotically slower algorithm.

stephencanon 13y ago
The crucial point is that two algorithms with the same asymptotic complexity may have radically different performance characteristics; if algorithm A asymptotically "always” hits L1, and algorithm B asymptotically “never” hits L1, then A may very well be bound purely by compute resources and B may be entirely bound by memory hierarchy throughput, despite the fact that they perform the same number of computations and memory accesses. Yes, this effect will always eventually be overtaken by wins in asymptotic complexity, but (as is often the case when matrix multiplication is involved) the constants may be such that reaching the crossover requires such comically large inputs as to render such considerations essentially negligible.
- betterunix 13y ago
  "The crucial point is that two algorithms with the same asymptotic complexity may have radically different performance characteristics" OK, but this was not a thread about the difference in constant factors, and I freely admit that constant factors matter. As I said elsewhere, twice as fast is twice as fast, there is no denying that. Strassen's algorithm does not have the same asymptotic performance as the textbook algorithm. Strassen's algorithm is faster at scale. "Yes, this effect will always eventually be overtaken by wins in asymptotic complexity, but (as is often the case when matrix multiplication is involved) the constants may be such that reaching the crossover requires such comically large inputs as to render such considerations essentially negligible." It sounds like you are confusing the best known matrix multiplication algorithm, William's algorithm, with Strassen's algorithm. Strassen's algorithm is used in practice, and depending on what sort of architecture you are on the crossover point is N being in the hundreds or the thousands (for an NxN matrix). These are not comically large, these are sizes that are seen in practice in various settings.

stephencanon 13y ago

The crucial point is that two algorithms with the same asymptotic complexity may have radically different performance characteristics; if algorithm A asymptotically "always” hits L1, and algorithm B asymptotically “never” hits L1, then A may very well be bound purely by compute resources and B may be entirely bound by memory hierarchy throughput, despite the fact that they perform the same number of computations and memory accesses. Yes, this effect will always eventually be overtaken by wins in asymptotic complexity, but (as is often the case when matrix multiplication is involved) the constants may be such that reaching the crossover requires such comically large inputs as to render such considerations essentially negligible.

betterunix 13y ago
"The crucial point is that two algorithms with the same asymptotic complexity may have radically different performance characteristics" OK, but this was not a thread about the difference in constant factors, and I freely admit that constant factors matter. As I said elsewhere, twice as fast is twice as fast, there is no denying that. Strassen's algorithm does not have the same asymptotic performance as the textbook algorithm. Strassen's algorithm is faster at scale. "Yes, this effect will always eventually be overtaken by wins in asymptotic complexity, but (as is often the case when matrix multiplication is involved) the constants may be such that reaching the crossover requires such comically large inputs as to render such considerations essentially negligible." It sounds like you are confusing the best known matrix multiplication algorithm, William's algorithm, with Strassen's algorithm. Strassen's algorithm is used in practice, and depending on what sort of architecture you are on the crossover point is N being in the hundreds or the thousands (for an NxN matrix). These are not comically large, these are sizes that are seen in practice in various settings.