4 ms·

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 pur

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?

ovi256 6y ago
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.
- MPSimmons 6y ago
  Agree. I don't think we'll notice, but the next gen of CUDA will be better because of it.
  - amluto 6y ago
    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.
    - ovi256 6y ago
      Hopefully the matmul implementation can check matrix size and pick the algorithm to use from that. I think some may already do this.
nonameiguess 6y ago
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 https://en.wikipedia.org/wiki/Galactic_algorithm.
sdenton4 6y ago
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.
- taxemeEvasion 6y ago
  Strassen's is sometimes competitive in the thousands! https://www.cs.utexas.edu/users/flame/pubs/FLAWN79.pdf 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
- nonameiguess 6y ago
  Crap. I should have refreshed the page. Didn't see you already posted what I did.

ovi256 6y ago

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.

MPSimmons 6y ago
Agree. I don't think we'll notice, but the next gen of CUDA will be better because of it.
- amluto 6y ago
  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.
  - ovi256 6y ago
    Hopefully the matmul implementation can check matrix size and pick the algorithm to use from that. I think some may already do this.

nonameiguess 6y ago

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 https://en.wikipedia.org/wiki/Galactic_algorithm.

sdenton4 6y ago

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.

taxemeEvasion 6y ago
Strassen's is sometimes competitive in the thousands! https://www.cs.utexas.edu/users/flame/pubs/FLAWN79.pdf 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
nonameiguess 6y ago
Crap. I should have refreshed the page. Didn't see you already posted what I did.