Hacker News Reader

Comment by JulianChastain | Hacker News Reader

The article doesn't specify, and I don't have the prior knowledge to understand the paper; Is there a coded implementation of this in some language or is it purely a mathematical description of how theoretically multiplication can always be done with slightly fewer multiplications?

View on HN

Strassen's algorithm is still the fastest to be widely implemented. The Coppersmith-Winograd variants that have achieved better asymptotic complexity are all galactic algorithms: https://en.wikipedia.org/wiki/Galactic_algorithm.

The last time I paid attention to this stuff ten years ago, the operations were 'galactic' to get to these theoretical bounds. Constant terms such that you'd need matrices with n = many billions to start to be competitive with normal matmul or Strassen.

Strassen's is sometimes competitive in the thousands!

https://www.cs.utexas.edu/users/flame/pubs/FLAWN79.pdf

You're right though afaik all the other algorithms are still 'galactic' and completely impractical

Crap. I should have refreshed the page. Didn't see you already posted what I did.

I think the way it'll go is: it'll be implemented in Fotran, BLAS and so on until it percolates to numpy / CUDA so mortals like us can use it.

Agree. I don't think we'll notice, but the next gen of CUDA will be better because of it.

These particular algorithms tend to have large Constance factors, so you need astronomically large matrices before they become faster than algorithms with worse exponents but better constant factors.

Hopefully the matmul implementation can check matrix size and pick the algorithm to use from that. I think some may already do this.

Reply on news.ycombinator.com