7 ms·

This is not a correct summary of the results of the paper. First, you cut out the initial part of the sentence about improving on Strassen's two-level algorith

This is not a correct summary of the results of the paper. First, you cut out the initial part of the sentence about improving on Strassen's two-level algorithm. Here is the complete sentence: > Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. That is, note that the improvement cited in the latter part of the sentence is for the 4 x 4 matrix case. But then your next quote is not in reference to 4 x 4 matrices. That is, for larger matrix sizes, the best algorithm AlphaTensor discovered had the same theoretical complexity as Strassen-square, but better performance. EDIT: my next comments are confused and best ignored. See reply from pxx below. For the 4 x 4 matrix case, the theoretical complexity of AlphaTensor's algorithm was O(N^2.778) compared with the Strassen algorithm's complexity of O(N^2.8074), which is an improvement.

dgacmu 4y ago
In Z_2 - modular matrix multiplication, not conventional matrix multiplication. And in this case, modular over what I assume is GF(2), i.e., single bits.
- aaaaaaaaaaab 4y ago
  Modular multiplication over GF(2)… also known as AND?
pxx 4y ago
what, no, you have this all wrong. the complexity of multiplying two 4x4 matrices is clearly constant. the important thing about the constant, however, is that you can use this primitive on the block matrices recursively to possibly improve the asymptotic complexity. the complexity improvement in this paper is for arithmetic in Z_2 (modular arithmetic over single bits). in standard arithmetic, there is no asymptotic complexity improvement but the developed algorithms involve more efficiently fusible[0] operations, which is useful for the target hardware. [0] ed: this used to read 'with fewer multiplications,' which is clearly wrong: fewer multiplications would lower complexity. Interestingly, the discovered algorithm seems to have a larger number of additions, but still runs faster.
- boole1854 4y ago
  You are correct. I will edit.
- a-dub 4y ago
  if you're in gf2 on a traditional cpu and care about wall clock time, i start to wonder how something like simd xors and parity would compare...
- ColinWright 4y ago
  I thought that savings on the number of multiplications leads to savings in complexity. For example, multiplying 2x2 matrices using 7 multiplications instead of 8 gives an improvement in complexity. See my comment here: https://news.ycombinator.com/item?id=33098192 https://news.ycombinator.com/item?id=33098192 It's possible that my understanding is completely wrong, but your comment is at odds with my other reading, so it would be useful to get some clarification.
  - sdenton4 4y ago
    This is correct, as I understand it. Most complexity measures are defined in terms of asymptotic behavior, so any specific finite algorithm has 'constant' complexity. This is an obviously unhelpful bit of pedantry in the theory side. In fact, it's as you say; we can compute a 'raw' complexity for a finite operation (eg, raw count of arithmetic ops), and then use that operation as a primitive to create an algorithm with an asymptotic complexity which depends directly on the finite operation's 'raw' complexity. (complexity theory, and specifically for matrix multiplication, is a great example of metrics becoming targets becoming bad incentives, a la Goodhart's Law. The so-called best algorithms are 'galactic' and therefore of no use to anyone. There's some fuzzy-headed hope that one day the people chasing the big-O exponent metric will come up with something practically useful, buuuuuut... you actually gotta work practical problem to solve the practical problem, and that requires different metrics. This seems to be what's motivating the work under discussion here.)
  - pxx 4y ago
    sorry; whoops, I don't know why I said multiplications there. I somehow thought the "more additions" somehow meant "fewer multiplications," but no, it's just "more additions but faster performance on target." edited. your other comment notes that for some shapes, even in standard arithmetic, they have found algorithms with fewer multiplications than best-known. but those don't seem to extend to an algorithm with better asymptotic complexity for multiplying general matrices. otherwise I'd assume they'd claim them :)
skybrian 4y ago
Isn’t multiplying two 4x4 matrices a finite problem? What does big O complexity mean in that case?
- adgjlsfhk1 4y ago
  any fixed size multiplication algorithm has a corresponding general algorithm where you recursively divide a matrix into blocks and treat each block as an element. for any nxn algorithm that takes k multiplications, this yields a general algorithm with runtime n^log_n(k)
- Rioghasarig 4y ago
  My understanding of this situation is that they found a way to multiply 4x4 matrices that requires fewer multiplications than Strassen's . This implies that that can generalize to a way to multiply n x n matrices with a better theoretical complexity than Strassen's algorithm.
Nihmie 4y ago
To be pedantic about this complexity estimate for the 4 x 4 case, both of them reduce to a O(1). If N == 4, it's a constant, so we have O(4^2.778) == O(4^2.8074) == O(1). Talking about scaling for a problem that has no scaling factor is a bit odd.
- vlovich123 4y ago
  If you have to process many such matrices, you’re not at O(1). I would imagine that’s what the O is referring to in this case.
  - cochne 4y ago
    If you look at it that way then any algorithm is just o(n) where n is the number of matrices. O does not care about constant factors
    - vlovich123 4y ago
      There's a better explanation here: https://fgiesen.wordpress.com/2022/10/06/on-alphatensors-new-matrix-multiplication-algorithms/ https://fgiesen.wordpress.com/2022/10/06/on-alphatensors-new... This is for matrix multiplication where elements are themselves 4x4 matrices. So yes, indeed this is about multiplying many many 4x4 matrices where N is the size of the outer matrix.
- est31 4y ago
  Yeah the paper uses O notation for complexity, but never when N is constant. For constant N and M, the paper uses the number of scalar multiplication operations performed as complexity measure. According to Figure 3, their algorithm has decreased the best known value from 49 to 47 for 4x4 matrices, and from 98 to 96 for 5x5 matrices (as well as some further state of the art improvements).
- throwawaymaths 4y ago
  To be pedantic, paper is very clear that O is calculated after decomposing arbitrarily large matrices to 4x4s.

dgacmu 4y ago

In Z_2 - modular matrix multiplication, not conventional matrix multiplication. And in this case, modular over what I assume is GF(2), i.e., single bits.

aaaaaaaaaaab 4y ago
Modular multiplication over GF(2)… also known as AND?

pxx 4y ago

what, no, you have this all wrong. the complexity of multiplying two 4x4 matrices is clearly constant. the important thing about the constant, however, is that you can use this primitive on the block matrices recursively to possibly improve the asymptotic complexity. the complexity improvement in this paper is for arithmetic in Z_2 (modular arithmetic over single bits). in standard arithmetic, there is no asymptotic complexity improvement but the developed algorithms involve more efficiently fusible[0] operations, which is useful for the target hardware. [0] ed: this used to read 'with fewer multiplications,' which is clearly wrong: fewer multiplications would lower complexity. Interestingly, the discovered algorithm seems to have a larger number of additions, but still runs faster.

boole1854 4y ago
You are correct. I will edit.
a-dub 4y ago
if you're in gf2 on a traditional cpu and care about wall clock time, i start to wonder how something like simd xors and parity would compare...
ColinWright 4y ago
I thought that savings on the number of multiplications leads to savings in complexity. For example, multiplying 2x2 matrices using 7 multiplications instead of 8 gives an improvement in complexity. See my comment here: https://news.ycombinator.com/item?id=33098192 https://news.ycombinator.com/item?id=33098192 It's possible that my understanding is completely wrong, but your comment is at odds with my other reading, so it would be useful to get some clarification.
- sdenton4 4y ago
  This is correct, as I understand it. Most complexity measures are defined in terms of asymptotic behavior, so any specific finite algorithm has 'constant' complexity. This is an obviously unhelpful bit of pedantry in the theory side. In fact, it's as you say; we can compute a 'raw' complexity for a finite operation (eg, raw count of arithmetic ops), and then use that operation as a primitive to create an algorithm with an asymptotic complexity which depends directly on the finite operation's 'raw' complexity. (complexity theory, and specifically for matrix multiplication, is a great example of metrics becoming targets becoming bad incentives, a la Goodhart's Law. The so-called best algorithms are 'galactic' and therefore of no use to anyone. There's some fuzzy-headed hope that one day the people chasing the big-O exponent metric will come up with something practically useful, buuuuuut... you actually gotta work practical problem to solve the practical problem, and that requires different metrics. This seems to be what's motivating the work under discussion here.)
- pxx 4y ago
  sorry; whoops, I don't know why I said multiplications there. I somehow thought the "more additions" somehow meant "fewer multiplications," but no, it's just "more additions but faster performance on target." edited. your other comment notes that for some shapes, even in standard arithmetic, they have found algorithms with fewer multiplications than best-known. but those don't seem to extend to an algorithm with better asymptotic complexity for multiplying general matrices. otherwise I'd assume they'd claim them :)

skybrian 4y ago

Isn’t multiplying two 4x4 matrices a finite problem? What does big O complexity mean in that case?

adgjlsfhk1 4y ago
any fixed size multiplication algorithm has a corresponding general algorithm where you recursively divide a matrix into blocks and treat each block as an element. for any nxn algorithm that takes k multiplications, this yields a general algorithm with runtime n^log_n(k)
Rioghasarig 4y ago
My understanding of this situation is that they found a way to multiply 4x4 matrices that requires fewer multiplications than Strassen's . This implies that that can generalize to a way to multiply n x n matrices with a better theoretical complexity than Strassen's algorithm.

Nihmie 4y ago

To be pedantic about this complexity estimate for the 4 x 4 case, both of them reduce to a O(1). If N == 4, it's a constant, so we have O(4^2.778) == O(4^2.8074) == O(1). Talking about scaling for a problem that has no scaling factor is a bit odd.

vlovich123 4y ago
If you have to process many such matrices, you’re not at O(1). I would imagine that’s what the O is referring to in this case.
- cochne 4y ago
  If you look at it that way then any algorithm is just o(n) where n is the number of matrices. O does not care about constant factors
  - vlovich123 4y ago
    There's a better explanation here: https://fgiesen.wordpress.com/2022/10/06/on-alphatensors-new-matrix-multiplication-algorithms/ https://fgiesen.wordpress.com/2022/10/06/on-alphatensors-new... This is for matrix multiplication where elements are themselves 4x4 matrices. So yes, indeed this is about multiplying many many 4x4 matrices where N is the size of the outer matrix.
est31 4y ago
Yeah the paper uses O notation for complexity, but never when N is constant. For constant N and M, the paper uses the number of scalar multiplication operations performed as complexity measure. According to Figure 3, their algorithm has decreased the best known value from 49 to 47 for 4x4 matrices, and from 98 to 96 for 5x5 matrices (as well as some further state of the art improvements).
throwawaymaths 4y ago
To be pedantic, paper is very clear that O is calculated after decomposing arbitrarily large matrices to 4x4s.