Number of elementary multiplications for multiplying 4x4 matrices
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$
