## page was renamed from Matrix/wikipehia ## page was renamed from Matrix/vikipehia ## page was copied from DnsTemplate ##master-page:HelpTemplate <> <> == 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 == history == {{{ On the asymptotic complexity of matrix multiplication Publisher: IEEE }}} ---- CategoryDns CategoryWatch CategoryTemplate