4 ms·

I love these types of improvements - I figure they don't really have a practical application (except for shaving a few milliseconds off ultra large matrices), b

I love these types of improvements - I figure they don't really have a practical application (except for shaving a few milliseconds off ultra large matrices), but they're a testament to human ingenuity and the desire to strive for perfection no matter how far out of reach.

UncleOxidant 3y ago
There's a hell of a lot of matrix multiplications going on in AI/ML. Shaving off a few milliseconds for ultra large matrices could save power and money for the big players like Google, Microsoft/OpenAI and Meta.
- imtringued 3y ago
  The bottleneck in those is not the arithmetic operation but the memory bandwidth once you have to spill your matrix out of SRAM. As it stands right now, it is actually better to have a slower algorithm that uses the local memory more efficiently.
- amanda99 3y ago
  Those are by and large many small matrices being multiplied, these results have nothing to do with that.
amanda99 3y ago
No, these aren't practical algorithms. No one uses them in reality. The hope is that these small improvements will lead to new insights that will then lead to big improvements. I doubt how matrix multiplication will be done will really change regardless of these theoretical results, unless something really groundbreaking and shocking is discovered. It's all relatively pretty in the grand scheme of things.
- hinkley 3y ago
  I think the last thing I saw on matrices was looking toward optimizing slightly larger sub-problems. That smells a little bit like a loop unrolling and/or locality improvement to me, You can often beat a theoretical algorithmic improvement with a practical one in such situations. And if you do a little bit of both you hopefully end up with something that's faster than the current most practical implementation.
jcranmer 3y ago
Strassen's algorithm is rarely used: its primary use, to my understanding, is in matrix algorithms of more exotic fields than reals or complex numbers, where minimizing multiplies is extremely useful. Even then, Strassen only starts to beat out naive matrix multiply when you're looking at n >= 1000's--and at that size, you're probably starting to think about using sparse matrices where your implementation strategy is completely different. But for a regular dgemm or sgemm, it's not commonly used in BLAS implementations. The more advanced algorithms than Strassen's are even worse in terms of the cutover point, and are never seriously considered.
- taeric 3y ago
  How big are the matrixes in some modern training pipelines? We always talk of absurdly large parameter spaces.
  - ogogmad 3y ago
    SGD keeps the matrices small, I think.
- jedbrown 3y ago
  The cross-over can be around 500 (https://doi.org/10.1109/SC.2016.58 https://doi.org/10.1109/SC.2016.58) for 2-level Strassen. It's not used by regular BLAS because it is less numerically stable (a concern that becomes more severe for the fancier fast MM algorithms). Whether or not the matrix can be compressed (as sparse, fast transforms, or data-sparse such as the various hierarchical low-rank representations) is more a statement about the problem domain, though it's true a sizable portion of applications that produce large matrices are producing matrices that are amenable to data-sparse representations.

UncleOxidant 3y ago

There's a hell of a lot of matrix multiplications going on in AI/ML. Shaving off a few milliseconds for ultra large matrices could save power and money for the big players like Google, Microsoft/OpenAI and Meta.

imtringued 3y ago
The bottleneck in those is not the arithmetic operation but the memory bandwidth once you have to spill your matrix out of SRAM. As it stands right now, it is actually better to have a slower algorithm that uses the local memory more efficiently.
amanda99 3y ago
Those are by and large many small matrices being multiplied, these results have nothing to do with that.

amanda99 3y ago

No, these aren't practical algorithms. No one uses them in reality. The hope is that these small improvements will lead to new insights that will then lead to big improvements. I doubt how matrix multiplication will be done will really change regardless of these theoretical results, unless something really groundbreaking and shocking is discovered. It's all relatively pretty in the grand scheme of things.

hinkley 3y ago
I think the last thing I saw on matrices was looking toward optimizing slightly larger sub-problems. That smells a little bit like a loop unrolling and/or locality improvement to me, You can often beat a theoretical algorithmic improvement with a practical one in such situations. And if you do a little bit of both you hopefully end up with something that's faster than the current most practical implementation.

jcranmer 3y ago

Strassen's algorithm is rarely used: its primary use, to my understanding, is in matrix algorithms of more exotic fields than reals or complex numbers, where minimizing multiplies is extremely useful. Even then, Strassen only starts to beat out naive matrix multiply when you're looking at n >= 1000's--and at that size, you're probably starting to think about using sparse matrices where your implementation strategy is completely different. But for a regular dgemm or sgemm, it's not commonly used in BLAS implementations. The more advanced algorithms than Strassen's are even worse in terms of the cutover point, and are never seriously considered.

taeric 3y ago
How big are the matrixes in some modern training pipelines? We always talk of absurdly large parameter spaces.
- ogogmad 3y ago
  SGD keeps the matrices small, I think.
jedbrown 3y ago
The cross-over can be around 500 (https://doi.org/10.1109/SC.2016.58 https://doi.org/10.1109/SC.2016.58) for 2-level Strassen. It's not used by regular BLAS because it is less numerically stable (a concern that becomes more severe for the fancier fast MM algorithms). Whether or not the matrix can be compressed (as sparse, fast transforms, or data-sparse such as the various hierarchical low-rank representations) is more a statement about the problem domain, though it's true a sizable portion of applications that produce large matrices are producing matrices that are amenable to data-sparse representations.