Hacker News Reader

Comment by barbarr | Hacker News Reader

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.

View on HN

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.

How big are the matrixes in some modern training pipelines? We always talk of absurdly large parameter spaces.

SGD keeps the matrices small, I think.

The cross-over can be around 500 (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.

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.

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.

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.

Those are by and large many small matrices being multiplied, these results have nothing to do with that.

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.

Reply on news.ycombinator.com