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.
$\endgroup$2 Answers
$\begingroup$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.
$\endgroup$ 5 $\begingroup$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.
$\endgroup$
