4 ms·

Abstract: "In response to a recent Nature article which announced an algorithm for multiplying 5×5-matrices over ℤ2 with only 96 multiplications, two fewer than

Abstract: "In response to a recent Nature article which announced an algorithm for multiplying 5×5-matrices over ℤ2 with only 96 multiplications, two fewer than the previous record, we present an algorithm that does the job with only 95 multiplications." The "recent Nature article" is, of course, Deepmind's reinforcement learning-guided search for better matrix multiplication algorithms: https://news.ycombinator.com/item?id=33096580 https://news.ycombinator.com/item?id=33096580. They improved upon Deepmind's algorithms by applying a method of their own, which is not described in this paper, but which they will publish in an upcoming paper: "Manuel Kauers and Jakob Moosbauer. Flip graphs for matrix multiplication. in preparation."

ckemere 4y ago
Deep-learning-hype-hater-quick-take: Based on that title (and a glance at the paper), my guess is that rather than brute force and megawatts of GPU power, they found a first-principles solution.
- inasio 4y ago
  On that Google Nature paper, I'm not sure if the 5x5 matrix improvement is the more significant result, or that they figured out a way to optimize directly to SIMD/AVX instructions, resulting in faster execution even if not necessarily fewer operations
  - ncmncm 4y ago
    The result is not interesting for ordinary numbers, where the classical ("slower") method is faster. When each element of the 5x5 matrix is itself a matrix, it could be important. So AVX ops for the method are not interesting.
    - bodhiandphysics 4y ago
      No... using divide and conquer matrix multiplication with this gives n^2.83. Strassens algorithm is n^2.79. This is good fir 5 by 5 matrices... which are not terribly interesting.
      - ncmncm 4y ago
        It uses many more additions. When the elements are themselves matrices, additions are a lot cheaper than multiplications, so that is OK. But with ordinary numbers, additions cost about the same as multiplications, so trading off a few multiplications for a lot more additions loses.
    - vlovich123 4y ago
      I thought it was when you were multiplying two matrices where the elements are 5x5 rather than a 5x5 matrix containing embedded matrices of arbitrary length, no?
      - londons_explore 4y ago
        The technique works for either
        ncmncm 4y ago
        But usefully for only one.
- sdenton4 4y ago
  Their result is "We found a slightly better method after someone told us where to look." It's very common in mathematics for simpler proofs and extensions of results to follow an initial ground-breaking paper. People looking at this preprint as a refutation of the ML techniques have it exactly backwards.
- jltsiren 4y ago
  This seems to be a typical case of the following scenario: You have been working on a topic for a while. Then, one day, you learn that someone has managed to get a paper on the topic into Nature/Science/whatever. And not because their results are that impressive but because they are from a famous institute and are using fashionable methods. Of course, the first thing you do is checking if you can improve the results with the tools you already have. If you can, you post the results online and start working on a paper. That happens all the time.
- ForOldHack 4y ago
  A machine or any algorithm, by definition cannot be first principals. This term was coined with Richard Feynman, and ever since then, in all instances, it has been mis-used. "No official code found." There are known faster methods, that as yet are unproven, that will save giga-watts of power.
TremendousJudge 4y ago
So it's a teaser paper?
- mabbo 4y ago
  I think the point is to publish before anyone else does. If they wait until they're full paper is ready, they might be scooped.
  - Yajirobe 4y ago
    Are we calling dibs on research now? Is this a kindergarten?
    - girvo 4y ago
      Science/academia has been for as long as I can remember.
    - sidlls 4y ago
      Read some of the history around natural philosophy some few hundred years ago. It’s a real hoot, how petty and ego-driven some of these people were. Leibniz’s attempts at taking credit for Newton’s hard work come to mind. (Tongue somewhat planted in cheek here.) Research has always been about getting credit for first discovering something, to some extent.
    - mattkrause 4y ago
      Now?! Sorry, but someone called dibs on the idea of “priority” long, long ago. The oldest dispute on this list is in the 1500s: https://en.wikipedia.org/wiki/List_of_scientific_priority_disputes https://en.wikipedia.org/wiki/List_of_scientific_priority_di...
  - ReaLNero 4y ago
    I'm not sure how to feel about this. If the purpose of science research is to build the understanding we have, teaser articles seem more like a way to put a name on a creation without actually contributing to our understanding of something. I guess this is an artifact of how cutthroat academia is and how vital it is to have credit for being first.
naillo 4y ago
Hope they get a nature article as well.

ckemere 4y ago

Deep-learning-hype-hater-quick-take: Based on that title (and a glance at the paper), my guess is that rather than brute force and megawatts of GPU power, they found a first-principles solution.

inasio 4y ago
On that Google Nature paper, I'm not sure if the 5x5 matrix improvement is the more significant result, or that they figured out a way to optimize directly to SIMD/AVX instructions, resulting in faster execution even if not necessarily fewer operations
- ncmncm 4y ago
  The result is not interesting for ordinary numbers, where the classical ("slower") method is faster. When each element of the 5x5 matrix is itself a matrix, it could be important. So AVX ops for the method are not interesting.
  - bodhiandphysics 4y ago
    No... using divide and conquer matrix multiplication with this gives n^2.83. Strassens algorithm is n^2.79. This is good fir 5 by 5 matrices... which are not terribly interesting.
    - ncmncm 4y ago
      It uses many more additions. When the elements are themselves matrices, additions are a lot cheaper than multiplications, so that is OK. But with ordinary numbers, additions cost about the same as multiplications, so trading off a few multiplications for a lot more additions loses.
  - vlovich123 4y ago
    I thought it was when you were multiplying two matrices where the elements are 5x5 rather than a 5x5 matrix containing embedded matrices of arbitrary length, no?
    - londons_explore 4y ago
      The technique works for either
      - ncmncm 4y ago
        But usefully for only one.
sdenton4 4y ago
Their result is "We found a slightly better method after someone told us where to look." It's very common in mathematics for simpler proofs and extensions of results to follow an initial ground-breaking paper. People looking at this preprint as a refutation of the ML techniques have it exactly backwards.
jltsiren 4y ago
This seems to be a typical case of the following scenario: You have been working on a topic for a while. Then, one day, you learn that someone has managed to get a paper on the topic into Nature/Science/whatever. And not because their results are that impressive but because they are from a famous institute and are using fashionable methods. Of course, the first thing you do is checking if you can improve the results with the tools you already have. If you can, you post the results online and start working on a paper. That happens all the time.
ForOldHack 4y ago
A machine or any algorithm, by definition cannot be first principals. This term was coined with Richard Feynman, and ever since then, in all instances, it has been mis-used. "No official code found." There are known faster methods, that as yet are unproven, that will save giga-watts of power.

TremendousJudge 4y ago

So it's a teaser paper?

mabbo 4y ago
I think the point is to publish before anyone else does. If they wait until they're full paper is ready, they might be scooped.
- Yajirobe 4y ago
  Are we calling dibs on research now? Is this a kindergarten?
  - girvo 4y ago
    Science/academia has been for as long as I can remember.
  - sidlls 4y ago
    Read some of the history around natural philosophy some few hundred years ago. It’s a real hoot, how petty and ego-driven some of these people were. Leibniz’s attempts at taking credit for Newton’s hard work come to mind. (Tongue somewhat planted in cheek here.) Research has always been about getting credit for first discovering something, to some extent.
  - mattkrause 4y ago
    Now?! Sorry, but someone called dibs on the idea of “priority” long, long ago. The oldest dispute on this list is in the 1500s: https://en.wikipedia.org/wiki/List_of_scientific_priority_disputes https://en.wikipedia.org/wiki/List_of_scientific_priority_di...
- ReaLNero 4y ago
  I'm not sure how to feel about this. If the purpose of science research is to build the understanding we have, teaser articles seem more like a way to put a name on a creation without actually contributing to our understanding of something. I guess this is an artifact of how cutthroat academia is and how vital it is to have credit for being first.

naillo 4y ago

Hope they get a nature article as well.