5 ms·

A hand rolled routine where you benchmarked different indexing orders, strides, interleaving on a particular sized matrix on fixed sizes of caches has the poten

by danmg 8y ago

A hand rolled routine where you benchmarked different indexing orders, strides, interleaving on a particular sized matrix on fixed sizes of caches has the potential to outperform blas. In general, use BLAS. Those sub-cubic algorithms require the matrix to be very-very-very large to recoup the extra constant costs associated with them.

sampo 8y ago
> Those sub-cubic algorithms require the matrix to be very-very-very large to recoup the extra constant costs associated with them. Wikipedia disagrees: "In practice, Strassen's algorithm can be implemented to attain better performance than conventional multiplication even for small matrices, for matrices that are not at all square, and without requiring workspace beyond buffers that are already needed for a high-performance conventional multiplication." https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm
- danmg 8y ago
  That's not what I learned in grad school when I took a class on this.
  - sdenton4 8y ago
    I used to use Atlas quite a bit, which effectively benchmarks your CPU and memory configuration at installation time to empirically determine where to switch from 'small n' algorithms to asymptomatically optimal algorithms, like Strassen. Of course, if you only some resources into optimizing the cubic time version, Strassen will look slow by comparison. Better we take a serious look at both and empirically figure out where the trade off point is...
    - danmg 8y ago
      Yes atlas is good. For small, dense n you're not going to beat the cubic algorithm. This is the most common case in a lot of applications. For sparse n, use a sparse version of the cubic algorithm. For large dense n, those sub-cubic algorithms might be better. Here n would have to be so large that you'd have to factor in the cost of doing it out of core.
  - sampo 8y ago
    Wikipedia refers to this paper from 2016. https://dl.acm.org/citation.cfm?id=3014983 https://dl.acm.org/citation.cfm?id=3014983
    - danmg 8y ago
      If you actually read that paper, you'd see that they roughly achieved the same performance (GFlops) as the cubic algorithm when the normalized for the problem instance size. Please stop wikisplaining.

by danmg 8y ago

sampo 8y ago

> Those sub-cubic algorithms require the matrix to be very-very-very large to recoup the extra constant costs associated with them. Wikipedia disagrees: "In practice, Strassen's algorithm can be implemented to attain better performance than conventional multiplication even for small matrices, for matrices that are not at all square, and without requiring workspace beyond buffers that are already needed for a high-performance conventional multiplication." https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm

danmg 8y ago
That's not what I learned in grad school when I took a class on this.
- sdenton4 8y ago
  I used to use Atlas quite a bit, which effectively benchmarks your CPU and memory configuration at installation time to empirically determine where to switch from 'small n' algorithms to asymptomatically optimal algorithms, like Strassen. Of course, if you only some resources into optimizing the cubic time version, Strassen will look slow by comparison. Better we take a serious look at both and empirically figure out where the trade off point is...
  - danmg 8y ago
    Yes atlas is good. For small, dense n you're not going to beat the cubic algorithm. This is the most common case in a lot of applications. For sparse n, use a sparse version of the cubic algorithm. For large dense n, those sub-cubic algorithms might be better. Here n would have to be so large that you'd have to factor in the cost of doing it out of core.
- sampo 8y ago
  Wikipedia refers to this paper from 2016. https://dl.acm.org/citation.cfm?id=3014983 https://dl.acm.org/citation.cfm?id=3014983
  - danmg 8y ago
    If you actually read that paper, you'd see that they roughly achieved the same performance (GFlops) as the cubic algorithm when the normalized for the problem instance size. Please stop wikisplaining.