5 ms·

Matrix multiplication breakthrough could lead to faster, more efficient AI

31 points by jonbaer 3y ago

SeanAnderson 3y ago
The title of this article is pretty dubious given the relative improvement. For a 3x3 matrix, the naive approach requires 2^3 multiplications. The theoretical ideal lowest bound is 2^2. In 2020, our best was 2^2.3728596 and now our best is 2^2.371552... so, less than half a percent of an improvement
- Someone 3y ago
  > For a 3x3 matrix, the naive approach requires 2^3 multiplications 3^3. For a n×n matrix, it takes n^3. > The theoretical ideal lowest bound is 2^2. No, we know the exponent is at least 2, not that it is 2. I also think nobody thinks the exponent is 2, as that would mean we can multiply matrices with a single multiplication per value in the result (in this field, there isn’t even a “up to a constant factor” involved) Having said that, I think everybody thought the exponent was 3 until Strassen decreased it to 2log7.
  - SeanAnderson 3y ago
    > No, we know the exponent is at least 2, not that it is 2. From the article: "bringing it closer to the ideal value of 2, which represents the theoretical minimum number of operations needed." It's fine if the article is wrong. You sound informed. Just wanted to highlight the difference.
    - kadoban 3y ago
      The nuance here is that the best _proven_ lower bound is n^2. ~Everybody suspects that the real lower bound is higher, but nobody seems to know how to prove it.
randcraw 3y ago
I wonder how much change is needed to how we use GPUs for this to yield real gains. Can we revise libcuDNN (and other higher math libs) only, or CUDA itself? Or must GPU hardware change too?
ein0p 3y ago
Nobody uses these algorithms. It’s of a purely academic interest. The only fancy algebra that is actually used in AI (for convolution) is the Winograd transform. Some recent stuff uses FFT or similar approaches. Dense matmul however is very hard to beat, when implemented well, and billions of dollars have already been spent to make it go as fast as possible

31 points by jonbaer 3y ago

The title of this article is pretty dubious given the relative improvement. For a 3x3 matrix, the naive approach requires 2^3 multiplications. The theoretical ideal lowest bound is 2^2. In 2020, our best was 2^2.3728596 and now our best is 2^2.371552... so, less than half a percent of an improvement

Someone 3y ago
> For a 3x3 matrix, the naive approach requires 2^3 multiplications 3^3. For a n×n matrix, it takes n^3. > The theoretical ideal lowest bound is 2^2. No, we know the exponent is at least 2, not that it is 2. I also think nobody thinks the exponent is 2, as that would mean we can multiply matrices with a single multiplication per value in the result (in this field, there isn’t even a “up to a constant factor” involved) Having said that, I think everybody thought the exponent was 3 until Strassen decreased it to 2log7.
- SeanAnderson 3y ago
  > No, we know the exponent is at least 2, not that it is 2. From the article: "bringing it closer to the ideal value of 2, which represents the theoretical minimum number of operations needed." It's fine if the article is wrong. You sound informed. Just wanted to highlight the difference.
  - kadoban 3y ago
    The nuance here is that the best _proven_ lower bound is n^2. ~Everybody suspects that the real lower bound is higher, but nobody seems to know how to prove it.

randcraw 3y ago

I wonder how much change is needed to how we use GPUs for this to yield real gains. Can we revise libcuDNN (and other higher math libs) only, or CUDA itself? Or must GPU hardware change too?

ein0p 3y ago

Nobody uses these algorithms. It’s of a purely academic interest. The only fancy algebra that is actually used in AI (for convolution) is the Winograd transform. Some recent stuff uses FFT or similar approaches. Dense matmul however is very hard to beat, when implemented well, and billions of dollars have already been spent to make it go as fast as possible