5

Applying recursively Strassen's algorithm on 4x4 matrices results in 49 elementary multiplications.

Are there methods tailored for 4x4 matrices which can do better?

Links to articles are highly appreciated.

user92382
  • 219

3 Answers3

7

It is possible to multiply two $4\times 4$ matrix $A,B$ with only 48 multiplications. The main idea is due to Winograd, it can be found in Stothers' thesis, for istance. For any row $A_{i,*}=(x_1,x_2,x_3,x_4)$ of $A$, let $A^{(i)}$ be the ausiliary quantity: $$A^{(i)} = x_1 x_2 + x_3 x_4,$$ and for any column $B_{*,j}=(y_1,y_2,y_3,y_4)$ of $B$, let $B^{(j)}$ the ausiliary quantity: $$B^{(j)} = y_1 y_2 + y_3 y_4.$$ Since $(AB)_{i,j}$ is the dot product between $A_{i,*}$ and $B_{*,j}$, and: $$(AB)_{i,j} = (x_1+y_2)(x_2+y_1)+(x_3+y_4)(x_4+y_3)-A^{(i)}-B^{(j)},$$ we need $16$ multiplications to store the ausiliary quantities and just $32$ multiplications to compute $16$ dot products, so we only need $48$ multiplications to compute $AB$. It is also interesting to notice that, by regarding a $4^{k+1}\times 4^{k+1}$ matrix as a $4\times 4$ block matrix, where every block is a $4^k\times 4^k$ matrix, we get a recursive algorithm for size-$n$ matrix multiplication having asymptotic complexity $$ n^{\log_{4}48} = n^{2.79248125\ldots} $$ that is a little better than Strassen's.

I really wonder if it is possible to do better for the $4\times 4$ case. Landerman proved that $23$ multiplications are sufficient to compute the product between two $3\times 3$ matrix, and it is a long-standing (open) question if it is possible to do the same with $22$ multiplications.

Jack D'Aurizio
  • 353,855
  • The link appears to be dead. – Simply Beautiful Art Aug 30 '19 at 21:48
  • @SimplyBeautifulArt: link restored. – Jack D'Aurizio Aug 31 '19 at 11:50
  • I took a look at it, and interestingly extending this to a $6\times6$ matrix gives matrix multiplication in $\mathcal O(n^{\log_6(144)})\approx\mathcal O(n^{2.77371})$, which is a nice bound for something so simple. Extending by multiplying terms in pairs like here to higher order matrices does not seem to improve on this, however. – Simply Beautiful Art Sep 01 '19 at 02:14
  • First, thank you so much for this answer. (1) Can you say more specifically where it is mentioned in Stothers' thesis? (2) Am I getting it right that this 48-multiplication algorithm is not an usual rank-decomposition algorithm, in that the factors being multiplied involve terms read from different matrices (e.g. $x1 + y2$ is a sum of an entry from matrix A and an entry from matrix B) ? So is 49 still the best known bound on the rank of the "4x4 matrix multiplication" tensor ? – Benoit Jacob Jan 22 '21 at 04:19
  • I believe that Jack's above answer needs a correction: this 48-multiplications algorithm applies to $4\times4$ matrices over a commutative ring only, unlike the $2\times2$ Strassen algorithm which applies as well over noncommutative rings. So it cannot actually be used recursively to obtain a $O(n^{\log_4 48})$ algorithm as suggested in the above answer; it can not even be applied just once over matrix blocks of a fixed size larger than $1\times1$. – Benoit Jacob Jan 23 '21 at 02:10
3

"Are there methods tailored for 4x4 matrices which can do better?"

Today, Deepmind's AI system discovered better result with just 47 multiplications. Was this result known previously? Apparently not, paper claims so. In fact some sites do not even know 48 case (https://fmm.univ-lille.fr) and so does not Deepmind paper. It is non-commutative, i.e. the pure 47 multiplications. But it is modulo 2 (modular in this table https://user-images.githubusercontent.com/31514790/194261146-0bcfad2d-1f40-44b7-96c7-3f9b247905ac.jpg, but some like 3, 4, 5 are improved in normal arithmetic)

https://www.nature.com/articles/s41586-022-05172-4/figures/6

47multiplications

The text form for this algorithm/decomposition is as follows

00001111000110001000000000000000000000000000000
00000001111110000000000000000000000000100000000
11110001000110000000000000000000000000000000000
00000000000000110111011110111111010100010011011
00100000000100000000000100010000100000010110010
01000001000000000000110010000100010101000000000
01110001000100000000000100000000000110000000000
00000000000000000000010000110100011000010011000
00000111000010001000000000000000100000000010001
00000001000000001110000000001000000001000011100
00000010000010000000000001000001000110010000011
00000000000000000111000010001001001100010000000
00000000100101100100000000000000110000000001001
00000000111110000000000000001000010001000000000
00000000010010000000001110001100000010001000000
00000000000000110100001100000100001000000000011

00111100101100000000000000000000000000000000000
00000110000001110000000001000000100000000000011
00110000101101000000000000000000100000000100000
00000100000000001000000000110000100000000111100
01010101001000001000000000000000000000100000000
00000000011000000011000010001000000001001000100
00000000101001000000110000100000010001000001000
01010101000000001000100000000000000001000000100
10010110011010000000000000000000000000000000000
00000110011010000000000001000000000010001000000
00110000000000010000001100000000000010001100010
01010000000000000001100011000001000110000000000
00000000000001110111111011110111000000011101110
00000000000001110111000000000000001000000001100
00000000000000010000111010100100001000001000000
00000000000000000001000001110001001000010100010


10001000000000000000000000000010000000100000000
11110000000000000000110000110010000000000100000
00001110000000001011000001000011000000000000100
00000000111001110000001000000010000000101000000
10000010010010100110000000001010000000000000001
00000000000000010001001111000101001110011000010
00000000000000100111000001000011000000000000001
00000000000000110110001000001010000000001000000
00101000100100000000011100000110010000000000000
00000000000000000000011100110110000000000100000
00000000000001110100000000110000101000010111011
00000000000001110000011000000110010000000000000
01000001000000001000000000010011000100110010000
00000000000000000000110000110011000100010000000
00000000000000000011000000010011000000010010100
00000000000000000111110010101100011001000001100

Same for this russian (Makarov) result for 3x3: 22 multiplications, but the algorithm has both matrix A and B elements on both sides of multiplications (commutative algorithm), which makes it less usefull, cause you cannot use
it for block matrices https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=4056&option_lang=rus It is an open problem whether 21 is possible, but we know from Bläser (2013) that at least 19 multiplications are needed. The formula given by Bläser gives lower bond for 4x4 x 4x4 billinear component (i.e. multiplications) as 34.

P.S. This paper also reports 21 result for 3x3 x 3x3: https://arxiv.org/abs/1904.07683, it is of course also commutative! Also see this bigger review: https://arxiv.org/abs/2206.00550

Валерий Заподовников
  • 171
  • This is a mod2 result. That is, the rank is 47 only if you are working over Z/2Z. It is a pity that the Nature paper did not make this clear. – Symbol 1 Oct 06 '22 at 02:42
  • So this is garbage result? – Валерий Заподовников Oct 06 '22 at 02:44
  • I wouldn't say that although I fell for that. It is important that people can easily find the "BUT WAIT..." statement on the internet so they are not misinformed by Nature. I strongly recommend you (and the community) not to delete this answer. – Symbol 1 Oct 06 '22 at 03:33
  • I already edited wikipedia by mentioning 21 result for commutative case (also edited my post here) that was found recently and I added 47 Z/2Z case. Please check out https://en.wikipedia.org/wiki/Computational_complexity_of_matrix_multiplication Please also give me a result that fails not over Z/2Z. I will report it to Deepmind. – Валерий Заподовников Oct 06 '22 at 03:46
  • DeepMind knows this is a mod-2 result. They said that in the paper just not at places you will be looking at when you are lead to the paper by the media. Also, choosing to attack mod-2 tensors is a good move because SAT/SMT solvers loves mod-2. – Symbol 1 Oct 06 '22 at 03:49
  • Did you see https://arxiv.org/abs/1904.07683? It has actual 21 result, commutative! Still cool! – Валерий Заподовников Oct 06 '22 at 03:52
  • 1
    1904.97683 is a commutative <3, 3, 3; 21>. Ladderman's uncommutative <3, 3, 3, 23> is still the best result. Authors really should learn the lessons and specify things more clearly. – Symbol 1 Oct 06 '22 at 03:55
  • I know that 1904.97683 is commutative. It improves on Makarov, which is commutative. Still, this IS a result. Even if it cannot be applied for block matrices. The fact is lower bond is 19. It is still an open problem. – Валерий Заподовников Oct 06 '22 at 04:11
  • Wait a second. The paper also talks how it discovered 58 for (3, 5, 5), the same algorithm as was discovered by Sedoglavic and Smirnov in 2021. Are you saying it is also just mod2? Then why is that equvivalent? – Валерий Заподовников Oct 06 '22 at 05:14
  • So! Even though for (4, 4, 4) it is indeed only modular arithmetic, for (3, 4, 5) it is both normal and modular. https://user-images.githubusercontent.com/31514790/194261146-0bcfad2d-1f40-44b7-96c7-3f9b247905ac.jpg – Валерий Заподовников Oct 07 '22 at 19:47
  • BTW, one of Z/2Z results already improved for (5, 5, 5) https://arxiv.org/pdf/2210.04045.pdf – Валерий Заподовников Oct 28 '22 at 18:18
1

This may not be optimal for $4 \times 4$ matrices. But eventually for large matrices, the CopperSmith Winograd algorithm (which has now been improved slightllllly) will perform lesser number of multiplications.