Contents
1. Matrix Multiply
Minimizing number of multiplications
Related to the problem of minimizing the number of arithmetic operations is
minimizing the number of multiplications, which is typically a more costly operation than addition.
A O ( n ω ) {\displaystyle O(n^{\omega })} algorithm for matrix multiplication must necessarily only use
O ( n ω ) {\displaystyle O(n^{\omega })} multiplication operations,
but these algorithms are impractical.
Improving from the naive n 3 n^{3} multiplications for schoolbook multiplication,
4 × 4 4\times 4 matrices in Z / 2 Z \mathbb {Z} /2\mathbb {Z} can be done with 47 multiplications,[33]
3 × 3 3\times 3 matrix multiplication over a commutative ring can be done in 21 multiplications[34][35]
(23 if non-commutative[36]).
The lower bound of multiplications needed is 2mn+2n−m−2
(multiplication of n×m-matrices with m×n-matrices using the substitution method, m⩾n⩾3),
which means n=3 case requires at least 19 multiplications and n=4 at least 34.
[37] For n=2 optimal 7 multiplications 15 additions are minimal, compared to only 4 additions for 8 multiplications.
[38][39] https://arxiv.org/abs/2210.10173
D. Coppersmith; S. Winograd https://ieeexplore.ieee.org/document/4568320
2. history
On the asymptotic complexity of matrix multiplication Publisher: IEEE