News for hackers. Stuff that matters.

A comment on Matrix multiplication inches closer to mythic goal.

Re:Matrix multiplication inches closer to mythic goal by JulianChastain on Tuesday March 23, 2021 @11:24AM (#26556106)
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?
[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by nonameiguess on Tuesday March 23, 2021 @12:06PM (#26556638)
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.
[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by sdenton4 on Tuesday March 23, 2021 @11:43AM (#26556359)
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.
[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by taxemeEvasion on Tuesday March 23, 2021 @11:56AM (#26556520)
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

[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by nonameiguess on Tuesday March 23, 2021 @12:07PM (#26556649)
Crap. I should have refreshed the page. Didn't see you already posted what I did.
[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by ovi256 on Tuesday March 23, 2021 @11:34AM (#26556217)
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.
[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by MPSimmons on Tuesday March 23, 2021 @11:40AM (#26556299)
Agree. I don't think we'll notice, but the next gen of CUDA will be better because of it.
[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by amluto on Tuesday March 23, 2021 @11:54AM (#26556503)
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.
[ Parent | on HN ]
Re:Matrix multiplication inches closer to mythic goal by ovi256 on Wednesday March 24, 2021 @05:09AM (#26564999)
Hopefully the matmul implementation can check matrix size and pick the algorithm to use from that. I think some may already do this.
[ Parent | on HN ]