Content deleted Content added
→Minimizing number of multiplications: added ibfo about additions |
|||
Line 300:
===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 <math>O(n^\omega)</math> algorithm for matrix multiplication must necessarily only use <math>O(n^\omega)</math> multiplication operations, but these algorithms are impractical. Improving from the naive <math>n^3</math> multiplications for schoolbook multiplication, <math>4\times 4</math> matrices in <math>\mathbb{Z}/2\mathbb{Z}</math> can be done with 47 multiplications<ref>{{Cite journal |title=Extended Data Fig. 1: Algorithm for multiplying 4 × 4 matrices in modular arithmetic (\({{\mathbb{Z}}}_{2}\)) with 47 multiplications. {{!}} Nature |url=https://www.nature.com/articles/s41586-022-05172-4/figures/6?as=jpg |language=en}}</ref>, <math>3\times 3</math> matrix multiplication over a commutative ring can be done in 21 multiplications<ref>{{Cite journal |last=Rosowski |first=Andreas |date=2020-07-27 |title=Fast Commutative Matrix Algorithm |url=http://arxiv.org/abs/1904.07683 |journal=arXiv:1904.07683 [cs]}}</ref><ref>{{cite web |title=О. М. Макаров, “Алгоритм умножения матриц размера $3\times 3$”, Ж. вычисл. матем. и матем. физ., 26:2 (1986), 293–294; Comput. Math. Math. Phys., 26:1 (1986), 179–180 |url=https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=zvmmf&paperid=4056&option_lang=rus |access-date=5 October 2022 |website=www.mathnet.ru}}</ref> (23 if non-commutative<ref>{{Cite journal |last=Laderman |first=Julian D. |date=1976 |title=A noncommutative algorithm for multiplying 3×3 matrices using 23 multiplications |url=https://www.ams.org/bull/1976-82-01/S0002-9904-1976-13988-2/ |journal=Bulletin of the American Mathematical Society |language=en |volume=82 |issue=1 |pages=126–128 |doi=10.1090/S0002-9904-1976-13988-2 |issn=0002-9904}}</ref>). The lower bound of multiplications needed is 2''mn''+2''n''−''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.<ref>{{Cite journal |last=Bläser |first=Markus |date=February 2003 |title=On the complexity of the multiplication of matrices of small formats |url=https://linkinghub.elsevier.com/retrieve/pii/S0885064X02000079 |journal=Journal of Complexity |language=en |volume=19 |issue=1 |pages=43–60 |doi=10.1016/S0885-064X(02)00007-9}}</ref> For n=2 7
==See also==
| |||