3 ms·

From the paper, "Notably, for multiplying two 4 × 4 matrices, applying the algorithm of Strassen recursively results in an algorithm with 49 multiplications, wh

From the paper, "Notably, for multiplying two 4 × 4 matrices, applying the algorithm of Strassen recursively results in an algorithm with 49 multiplications, which works over any field...AlphaEvolve is the first method to find an algorithm to multiply two 4 × 4 complex-valued matrices using 48 multiplications." If you do naive matrix multiplication, you get a sense that you're doing similar work multiple times, but it's hard to quantify just what that duplicated work entails. Compare it to, for example, calculating the size of the union of two sets: Total size = size(A) + size(B) - size(intersection(A, B)) You have to take out that extra intersection amount because you've counted it twice. What if you could avoid counting it twice in the first place? That's easy, you just iterate over each set once, keeping track of the elements you've already seen. Strassen's algorithm keeps track of calculations that are needed later on. It's all reminiscent of dynamic programming. What I find interesting is that it seems the extra savings requires complex values. There must be something going on in the complex plane that is again over-counting with the naive approach.

jackpirate 1y ago
It seems like you have some misconceptions about Strassen's alg: 1. It is a standard example of the divide and conquer approach to algorithm design, not the dynamic programming approach. (I'm not even sure how you'd squint at it to convert it into a dynamic programming problem.) 2. Strassen's does not require complex valued matrices. Everything can be done in the real numbers.
- kenjackson 1y ago
  I think the original poster was referring to the AlphaEvolve variant of Strassen's, not the standard Strassen (with respect to complex values).
- pontus 1y ago
  I think the OP was pointing out that the reason Strasssen's algorithm works is that it somehow uncovered a kind of repeated work that's not evident in a simple divide and conquer approach. It's by the clever definition of the various submatrices that this "overlapping" work can be avoided. In other words, the power of Strasssens algorithm comes from a strategy that's similar to / reminiscent of dynamic programming.
lf88 1y ago
By googling "4x4 matrices multiplication 48" I ended up on this discussion on math.stackexchange https://math.stackexchange.com/questions/578342/number-of-elementary-multiplications-for-multiplying-4x4-matrices https://math.stackexchange.com/questions/578342/number-of-el... , where in 2019 someone stated "It is possible to multiply two 4×4 matrix A,B with only 48 multiplications.", with a link to a PhD thesis. This might mean that the result was already known (I still have to check the outline of the algorithm).
- robinhouston 1y ago
  From some conversations on Twitter, it seems plausible that the rank-48 decomposition of the 4×4 matrix multiplication tensor really is new; and that perhaps where things have gone awry is attempting to summarise this result in a more lay-friendly manner: the algorithm in that post apparently doesn't constitute or imply a rank-48 tensor decomposition. On the other side, it's claimed here that an algorithm that uses only 46 multiplications has been known since 1970: https://mathstodon.xyz/@fredrikj/114508287537669113 https://mathstodon.xyz/@fredrikj/114508287537669113
  - looofooo0 1y ago
    Ironically their AI can cite the relevant paper with 46 steps if asked: https://gemini.google.com/share/b0d5d6a76c87 https://gemini.google.com/share/b0d5d6a76c87
- wbhart 1y ago
  As already noted in a post by fdej further down, Waksman's algorithm from 1970, which works over the complex numbers, requires only 46 multiplications (and I guess, divisions by 2, which may or may not be relevant depending on your actual ring).
  - nemonemo 1y ago
    The answer says "For rings in which division by 2 is permitted". Is there the same constraint for AlphaEvolve's algorithm? Edit2: Z_2 has characteristics 2. Edit: AlphaEvolve claims it works over any field with characteristic 0. It appears Waksman's could be an existing work. From the AlphaEvolve paper: "For 56 years, designing an algorithm with fewer than 49 multiplications over any field with characteristic 0 was an open problem. AlphaEvolve is the first method to find an algorithm to multiply two 4 × 4 complex-valued matrices using 48 multiplications."
Davidzheng 1y ago
Are you sure the saving needs complex values? I think their algorithm works over any char 0 field. Probably needs to just divide by some divisor of 4!=24 if I had to guess.
- meindnoch 1y ago
  Their decomposition of the (4,4,4) matrix multiplication tensor is explicitly listed in their Colab notebook, and it contains complex numbers.
Zr01 1y ago
A complex multiplication is "worth" at least 3 real multiplications.
- alexnovikov 1y ago
  Fair point! A single complex multiplication `(a+bi)(c+di)` indeed requires at least 3 real multiplications to be implemented. However, when researchers (and systems like AlphaEvolve in this context) analyze fast matrix multiplication algorithms like Strassen's, the primary goal is usually to improve the asymptotic complexity (and understand the space of these algorithms better). This complexity is determined by the number of multiplications in the field over which the matrices are defined. * For real matrices, we count real scalar multiplications. * For complex-valued matrices (as in the 4x4 example where AlphaEvolve found a solution with 48 scalar multiplications), "scalar multiplication" refers to a complex scalar multiplication. The key is that these are the operations you recurse on. Additions, or the constant factor cost of implementing one field's multiplication, don't change the exponent in the `N^(log_base(multiplications))` complexity. They are constant factors. Of course, for practical performance on a specific 4x4 matrix, one would absolutely dive into the real operations, additions, memory layout, etc., but making 4x4 matrix multiplication practically faster on some particular hardware was not the focus in this section. (We do improve practical implementation of large matrix multiplications on the target hardware in the “Enhancing AI training and inference” section of the blog post.) (Disclaimer: one of the authors.)
meindnoch 1y ago
>What I find interesting is that it seems the extra savings requires complex values. There must be something going on in the complex plane that is again over-counting with the naive approach. "The rank of a tensor depends on the field over which the tensor is decomposed. It is known that some real tensors may admit a complex decomposition whose rank is strictly less than the rank of a real decomposition of the same tensor." https://en.wikipedia.org/wiki/Tensor_rank_decomposition#Field_dependence https://en.wikipedia.org/wiki/Tensor_rank_decomposition#Fiel...

jackpirate 1y ago

It seems like you have some misconceptions about Strassen's alg: 1. It is a standard example of the divide and conquer approach to algorithm design, not the dynamic programming approach. (I'm not even sure how you'd squint at it to convert it into a dynamic programming problem.) 2. Strassen's does not require complex valued matrices. Everything can be done in the real numbers.

kenjackson 1y ago
I think the original poster was referring to the AlphaEvolve variant of Strassen's, not the standard Strassen (with respect to complex values).
pontus 1y ago
I think the OP was pointing out that the reason Strasssen's algorithm works is that it somehow uncovered a kind of repeated work that's not evident in a simple divide and conquer approach. It's by the clever definition of the various submatrices that this "overlapping" work can be avoided. In other words, the power of Strasssens algorithm comes from a strategy that's similar to / reminiscent of dynamic programming.

lf88 1y ago

By googling "4x4 matrices multiplication 48" I ended up on this discussion on math.stackexchange https://math.stackexchange.com/questions/578342/number-of-elementary-multiplications-for-multiplying-4x4-matrices https://math.stackexchange.com/questions/578342/number-of-el... , where in 2019 someone stated "It is possible to multiply two 4×4 matrix A,B with only 48 multiplications.", with a link to a PhD thesis. This might mean that the result was already known (I still have to check the outline of the algorithm).

robinhouston 1y ago
From some conversations on Twitter, it seems plausible that the rank-48 decomposition of the 4×4 matrix multiplication tensor really is new; and that perhaps where things have gone awry is attempting to summarise this result in a more lay-friendly manner: the algorithm in that post apparently doesn't constitute or imply a rank-48 tensor decomposition. On the other side, it's claimed here that an algorithm that uses only 46 multiplications has been known since 1970: https://mathstodon.xyz/@fredrikj/114508287537669113 https://mathstodon.xyz/@fredrikj/114508287537669113
- looofooo0 1y ago
  Ironically their AI can cite the relevant paper with 46 steps if asked: https://gemini.google.com/share/b0d5d6a76c87 https://gemini.google.com/share/b0d5d6a76c87
wbhart 1y ago
As already noted in a post by fdej further down, Waksman's algorithm from 1970, which works over the complex numbers, requires only 46 multiplications (and I guess, divisions by 2, which may or may not be relevant depending on your actual ring).
- nemonemo 1y ago
  The answer says "For rings in which division by 2 is permitted". Is there the same constraint for AlphaEvolve's algorithm? Edit2: Z_2 has characteristics 2. Edit: AlphaEvolve claims it works over any field with characteristic 0. It appears Waksman's could be an existing work. From the AlphaEvolve paper: "For 56 years, designing an algorithm with fewer than 49 multiplications over any field with characteristic 0 was an open problem. AlphaEvolve is the first method to find an algorithm to multiply two 4 × 4 complex-valued matrices using 48 multiplications."

Davidzheng 1y ago

Are you sure the saving needs complex values? I think their algorithm works over any char 0 field. Probably needs to just divide by some divisor of 4!=24 if I had to guess.

meindnoch 1y ago
Their decomposition of the (4,4,4) matrix multiplication tensor is explicitly listed in their Colab notebook, and it contains complex numbers.

Zr01 1y ago

A complex multiplication is "worth" at least 3 real multiplications.

alexnovikov 1y ago
Fair point! A single complex multiplication `(a+bi)(c+di)` indeed requires at least 3 real multiplications to be implemented. However, when researchers (and systems like AlphaEvolve in this context) analyze fast matrix multiplication algorithms like Strassen's, the primary goal is usually to improve the asymptotic complexity (and understand the space of these algorithms better). This complexity is determined by the number of multiplications in the field over which the matrices are defined. * For real matrices, we count real scalar multiplications. * For complex-valued matrices (as in the 4x4 example where AlphaEvolve found a solution with 48 scalar multiplications), "scalar multiplication" refers to a complex scalar multiplication. The key is that these are the operations you recurse on. Additions, or the constant factor cost of implementing one field's multiplication, don't change the exponent in the `N^(log_base(multiplications))` complexity. They are constant factors. Of course, for practical performance on a specific 4x4 matrix, one would absolutely dive into the real operations, additions, memory layout, etc., but making 4x4 matrix multiplication practically faster on some particular hardware was not the focus in this section. (We do improve practical implementation of large matrix multiplications on the target hardware in the “Enhancing AI training and inference” section of the blog post.) (Disclaimer: one of the authors.)

meindnoch 1y ago

>What I find interesting is that it seems the extra savings requires complex values. There must be something going on in the complex plane that is again over-counting with the naive approach. "The rank of a tensor depends on the field over which the tensor is decomposed. It is known that some real tensors may admit a complex decomposition whose rank is strictly less than the rank of a real decomposition of the same tensor." https://en.wikipedia.org/wiki/Tensor_rank_decomposition#Field_dependence https://en.wikipedia.org/wiki/Tensor_rank_decomposition#Fiel...