Перегляд вихідного коду сторінки Алгоритм перемножування матриць

{{short description|Алгоритм для перемножування матриць}}
{{Нерозв'язано|інформатики|Який алгоритм перемножування матриць є найшвидшим?}}
Оскільки [[множення матриць]] є настільки центральною операцією в багатьох [[Чисельний алгоритм|чисельних алгоритмах]], у те, щоби зробити '''алгори́тми перемно́жування ма́триць''' ефективними, було вкладено чимало праці. Застосування множення матриць в обчислювальних задачах зустрічаються в багатьох областях, включно з {{нп|Наукові обчислення|науковими обчисленнями||Scientific computing}} та [[Розпізнавання образів|розпізнаванням образів]], і в, здавалося би, не пов'язаних задачах, таких як підрахунок шляхів [[Граф (математика)|графом]].<ref name="skiena"/> Було розроблено багато різних алгоритмів для перемножування матриць на різних типах апаратного забезпечення, включно з [[Паралельні обчислення|паралельними]] та [[Розподілені обчислення|розподіленими]] системами, де обчислювальну працю розподілювано декількома процесорами (можливо, через мережу).

Безпосереднє застосування математичного означення множення матриць дає алгоритм, що для перемножування двох матриць {{math|''n'' × ''n''}} [[Аналіз алгоритмів|займає часу]] порядку {{math|''n''<sup>3</sup>}} (в [[Нотація Ландау|нотації Ландау]]&nbsp;— {{math|Θ(''n''<sup>3</sup>)}}). Кращі асимптотичні межі часу, необхідного для перемножування матриць, були відомі від часів праці Страссена 1960 року, але досі не відомо, яким є оптимальний час (тобто, якою є [[Теорія складності обчислень|складність цієї задачі]]).

== Ітеративний алгоритм ==

За [[Множення матриць#Визначення|означенням множення матриць]], якщо {{math|''C'' {{=}} ''AB''}} для матриці {{mvar|A}} розміру {{math|''n'' × ''m''}} та матриці {{mvar|B}} розміру {{math|''m'' × ''p''}}, то {{mvar|C}} є матрицею розміру {{math|''n'' × ''p''}} з елементами

: <math>c_{ij} = \sum_{k=1}^m a_{ik} b_{kj}</math>.

З цього може бути побудовано простий алгоритм, який обходить циклами індекси {{mvar|i}} з 1 по {{mvar|n}} та {{mvar|j}} з 1 по {{mvar|p}}, обчислюючи наведене вище із застосуванням вкладеного циклу:

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Вхід: матриці {{mvar|A}} та {{mvar|B}}
* Нехай {{mvar|C}} буде матрицею відповідного розміру
* Для {{mvar|i}} з 1 по {{mvar|n}}:
** Для {{mvar|j}} з 1 по {{mvar|p}}:
*** Нехай {{math|sum {{=}} 0}}
*** Для {{mvar|k}} з 1 по {{mvar|m}}:
**** Встановити {{math|sum ← sum + ''A<sub>ik</sub>'' × ''B<sub>kj</sub>''}}
*** Встановити {{math|''C<sub>ij</sub>'' ← sum}}
* Повернути {{mvar|C}}
{{frame-footer}}
</div>

Цей алгоритм займає [[Часова складність алгоритму|час]] {{math|Θ(''nmp'')}} (в [[Нотація Ландау|нотації Ландау]]).<ref name="skiena"/> Поширеним спрощенням для цілей [[Аналіз алгоритмів|аналізу алгоритмів]] є вважати, що всі входи є квадратними матрицями розміру {{math|''n'' × ''n''}}, в разі чого час виконання становить {{math|Θ(''n''<sup>3</sup>)}}, тобто, є кубічним.<ref name="clrs">{{CLRS|chapter=28 Дії над матрицями}}</ref>

=== Поведінка кешу ===
[[Файл:Порядковий та постовпчиковий порядок.svg|thumb|upright|Ілюстрація порядко́вого та постовпчикового порядку]]

Ці три цикли в ітеративному перемножуванні матриць можливо довільно переставляти між собою без впливу на правильність чи асимптотичну тривалість виконання. Проте цей порядок може мати значний вплив на практичну продуктивність через {{нп|Локальність посилань|моделі доступу до пам'яті||Locality of reference}} алгоритму та використання ним [[Кеш процесора|кешу]];<ref name="skiena">{{cite book |first=Steven |last=Skiena |authorlink=Стівен Скієна |title=The Algorithm Design Manual |url=https://archive.org/details/algorithmdesignm00skie_676 |publisher=Springer |year=2008 |pages=[https://archive.org/details/algorithmdesignm00skie_676/page/n56 45]–46, 401–403 |doi=10.1007/978-1-84800-070-4_4|chapter=Sorting and Searching |isbn=978-1-84800-069-8 }} {{ref-en}}</ref> який порядок є кращим також залежить від того, чи зберігаються матриці в {{нп|Порядковий порядок|порядко́вому порядку||Row-major order}}, постовпчиковому, чи суміші обох.

Зокрема, в ідеалізованому випадку [[Кеш процесора#Асоціативність|повністю асоціативного кешу]], складеного з {{mvar|M}} байтів та {{mvar|b}} байтів на рядок кешу (тобто, {{sfrac|''M''|''b''}} рядків кешу), наведений вище алгоритм є недооптимальним для {{mvar|A}} та {{mvar|B}}, що зберігаються в порядко́вому порядку. Коли {{math|''n'' > {{sfrac|''M''|''b''}}}}, кожна ітерація внутрішнього циклу (одночасного проходження рядком {{mvar|A}} та стовпчиком {{mvar|B}}) зазнає́ невлучання в кеш при отримуванні доступу до елементу {{mvar|B}}. Це означає, що цей алгоритм у найгіршому випадку зазнає {{math|Θ(''n''<sup>3</sup>)}} невлучань у кеш. {{As of|2010}} рік швидкість пам'яті в порівнянні зі швидкістю процесорів є такою, що для матриць значного розміру в тривалості виконання домінують невлучання в кеш, а не фактичні обчислення.<ref name="ocw">{{cite web|url=http://aka-ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/video-lectures/lecture-8-cache-efficient-algorithms/|title=6.172 Performance Engineering of Software Systems, Lecture 8|last1=Amarasinghe|first1=Saman|last2=Leiserson|first2=Charles|date=|year=2010|website=MIT OpenCourseWare|publisher=Massachusetts Institute of Technology|url-status=live|archive-url=https://web.archive.org/web/20191007160029/http://aka-ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/video-lectures/lecture-8-cache-efficient-algorithms/|archive-date=7 жовтня 2019|accessdate=27 січня 2015}} {{Webarchive|url=https://web.archive.org/web/20191007160029/http://aka-ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/video-lectures/lecture-8-cache-efficient-algorithms/ |date=2019-10-07 }} {{ref-en}}</ref>

Оптимальним варіантом ітеративного алгоритму для {{mvar|A}} та {{mvar|B}}, що зберігаються в порядку рядків, є {{нп|Розбивання циклу на блоки|''плиткова''||Loop tiling}} версія, в якій матрицю неявно ділять на квадратні плитки розміру {{math|{{radic|''M''}}}} на {{math|{{radic|''M''}}}}:<ref name="ocw"/><ref>{{cite conference |first1=Monica S. |last1=Lam |first2=Edward E. |last2=Rothberg |first3=Michael E. |last3=Wolf |title=The Cache Performance and Optimizations of Blocked Algorithms |conference=Int'l Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS) |year=1991}} {{ref-en}}</ref>

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Вхід: матриці {{mvar|A}} та {{mvar|B}}
* Нехай {{mvar|C}} буде матрицею відповідного розміру
* Обрати розмір плитки {{math|''T'' {{=}} Θ({{radic|''M''}})}}
* Для {{mvar|I}} з 1 по {{mvar|n}} кроками по {{mvar|T}}:
** Для {{mvar|J}} з 1 по {{mvar|p}} кроками по {{mvar|T}}:
*** Для {{mvar|K}} з 1 по {{mvar|m}} кроками по {{mvar|T}}:
**** Перемножити {{math|''A''<sub>''I'':''I''+''T'', ''K'':''K''+''T''</sub>}} та {{math|''B''<sub>''K'':''K''+''T'', ''J'':''J''+''T''</sub>}} до {{math|''C''<sub>''I'':''I''+''T'', ''J'':''J''+''T''</sub>}}, тобто:
**** Для {{mvar|i}} з {{mvar|I}} по {{math|min(''I'' + ''T'', ''n'')}}:
***** Для {{mvar|j}} з {{mvar|J}} по {{math|min(''J'' + ''T'', ''p'')}}:
****** Нехай {{math|sum {{=}} 0}}
****** Для {{mvar|k}} з {{mvar|K}} по {{math|min(''K'' + ''T'', ''m'')}}:
******* Встановити {{math|sum ← sum + ''A<sub>ik</sub>'' × ''B<sub>kj</sub>''}}
****** Встановити {{math|''C<sub>ij</sub>'' ← ''C<sub>ij</sub>'' + sum}}
* Повернути {{mvar|C}}
{{frame-footer}}
</div>

В ідеалізованій моделі кешу цей алгоритм зазнає лише {{math|Θ({{sfrac|''n''<sup>3</sup>|''b'' {{radic|''M''}}}})}} невлучань у кеш; дільник {{math|''b'' {{radic|''M''}}}} становить декілька порядків на сучасних машинах, тож у тривалості виконання домінують фактичні обчислення, а не невлучання в кеш.<ref name="ocw"/>

== Алгоритм «розділюй та володарюй» ==

Альтернативою до ітеративного алгоритму є [[алгоритм «розділюй та володарюй»]] для множення матриць. Він спирається на [[Блокова матриця|блокове розбиття]]

: <math>C = \begin{pmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22} \\
\end{pmatrix},\,
A = \begin{pmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22} \\
\end{pmatrix},\,
B = \begin{pmatrix}
B_{11} & B_{12} \\
B_{21} & B_{22} \\
\end{pmatrix}</math>,

яке працює для всіх квадратних матриць, чиї розміри є степенями двійки, тобто, форми {{math|2<sup>''n''</sup> × 2<sup>''n''</sup>}} для деякого {{mvar|n}}. Тепер добутком матриць є

: <math>\begin{pmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22} \\
\end{pmatrix} =
\begin{pmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22} \\
\end{pmatrix} \begin{pmatrix}
B_{11} & B_{12} \\
B_{21} & B_{22} \\
\end{pmatrix} = \begin{pmatrix}
A_{11} B_{11} + A_{12} B_{21} & A_{11} B_{12} + A_{12} B_{22}\\
A_{21} B_{11} + A_{22} B_{21} & A_{21} B_{12} + A_{22} B_{22}\\
\end{pmatrix}
</math>

що складається з восьми множень пар підматриць, з подальшим кроком додавання. Алгоритм «розділюй та володарюй» обчислює менші добутки [[Рекурсія|рекурсивно]], застосовуючи як основу [[скалярне множення]] {{math|''c''<sub>11</sub> {{=}} ''a''<sub>11</sub>''b''<sub>11</sub>}}.

Складність цього алгоритму як функції від {{mvar|n}} задається рекурентно як<ref name="clrs"/>

: <math>T(1) = \Theta(1)</math>;
: <math>T(n) = 8T(n/2) + \Theta(n^2)</math>,

із враховуванням восьми рекурсивних викликів на матрицях розміру {{math|''n''/2}}, та {{math|Θ(''n''<sup>2</sup>)}} для поелементного підсумовування чотирьох пар отримуваних в результаті матриць. Застосування [[Майстер-метод|майстер-методу для рекурсій «розділюй та володарюй»]] показує, що ця рекурсія має розв'язок {{math|Θ(''n''<sup>3</sup>)}}, такий же, як й ітеративний алгоритм.<ref name="clrs"/>

=== Неквадратні матриці ===

Варіант цього алгоритму, який працює для матриць довільних форм, і є швидшим на практиці,<ref name="ocw"/> розбиває матриці на дві замість чотирьох підматриць наступним чином.<ref name="prokop">{{cite thesis |type=Master's |first=Harald |last=Prokop |authorlink=Гаральд Прокоп |title=Cache-Oblivious Algorithms |publisher=MIT |year=1999 |url=http://supertech.csail.mit.edu/papers/Prokop99.pdf |accessdate=15 грудня 2019 |archive-date=24 листопада 2019 |archive-url=https://web.archive.org/web/20191124114139/http://supertech.csail.mit.edu/papers/Prokop99.pdf }} {{ref-en}}</ref> Розбивання матриці тепер означає поділ її на дві частини рівного розміру, або якомога ближче до рівних розмірів у разі, якщо розміри є непарними.

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
* Входи: матриці {{mvar|A}} розміру {{math|''n'' × ''m''}}, {{mvar|B}} розміру {{math|''m'' × ''p''}}.
* Базовий випадок: якщо {{math|max(''n'', ''m'', ''p'')}} є нижчим за певний поріг, застосувати [[Розмотування циклу|розмотану]] версію ітеративного алгоритму.
* Рекурсивні випадки:

:* Якщо {{math|max(''n'', ''m'', ''p'') {{=}} ''n''}}, розбити {{mvar|A}} горизонтально:

::<math>C = \begin{pmatrix} A_1 \\ A_2 \end{pmatrix} {B}
          = \begin{pmatrix} A_1 B \\ A_2 B \end{pmatrix}</math>

:* Інакше, якщо {{math|max(''n'', ''m'', ''p'') {{=}} ''p''}}, розбити {{mvar|B}} вертикально:

::<math>C = A \begin{pmatrix} B_1 & B_2 \end{pmatrix}
          = \begin{pmatrix} A B_1 & A B_2 \end{pmatrix}  </math>

:* Інакше, {{math|max(''n'', ''m'', ''p'') {{=}} ''m''}}. Робити {{mvar|A}} вертикально та {{mvar|B}} горизонтально:

::<math>C = \begin{pmatrix} A_1 & A_2 \end{pmatrix} \begin{pmatrix} B_1 \\ B_2 \end{pmatrix}
          = A_1 B_1 + A_2 B_2</math>
{{frame-footer}}
</div>

=== Поведінка кешу ===

Рівень невлучання в кеш в рекурсивного матричного множення є таким же, як і в {{нп|Розбивання циклу на блоки|плиткової||Loop tiling}} ітеративної версії, але, на відміну від того алгоритму, рекурсивний алгоритм є {{нп|Буферо-незалежний алгоритм|буферо-незалежним||Cache-oblivious algorithm}}:<ref name="prokop"/> він не має параметру налаштування, необхідного для досягнення оптимальної продуктивності кешу, і він добре поводиться в {{нп|Багатопрограмність|багатопрограмному||Multiprogramming}}<!-- Проблема вікіфікації: Сторінка [[:en:Multiprogramming]] (→ [[:en:Computer multitasking#Multiprogramming]]) перекладена як [[Багатозадачність]], хоча хотіли [[Багатопрограмність]] (SashkoR0B0T)--> середовищі, де розміри кешу є фактично динамічними через те, що інші процеси займають його простір.<ref name="ocw"/> (Простий ітеративний алгоритм також є буферо-незалежним, але набагато повільнішим на практиці, якщо компонування матриць не пристосовано до алгоритму.)

Кількість невлучань у кеш, що зазнає́ цей алгоритм на машині з {{mvar|M}} рядками ідеально кешу розміру {{mvar|b}} байтів кожен, обмежено{{r|prokop}}{{rp|13}}

: <math>\Theta \left(m + n + p + \frac{mn + np + mp}{b} + \frac{mnp}{b\sqrt{M}} \right)</math>

== Підкубічні алгоритми ==
[[Файл:Обмеження омеги перемножування матриць за часом.svg|thumb|400px|right|Найнижче {{mvar|ω}}, таке, що відомо, що множення матриць є в {{math|''O''(''n<sup>ω</sup>'')}}, відображене за часом.]]

Існують алгоритми, що забезпечують кращу тривалість виконання, ніж прямолінійні. Першим було відкрито [[алгоритм Штрассена]], винайдений [[Фолькер Штрассен|Фолькером Штрассеном]] 1969 року, який часто називають «швидким множенням матриць» ({{lang-en|"fast matrix multiplication"}}). Він ґрунтується на способі множення двох матриць {{math|2 × 2}}, який вимагає лише 7 множень (замість звичайних 8), ціною декількох додаткових операції додавання та віднімання. Його рекурсивне застосування дає алгоритм з витратами на множення <math>O( n^{\log_{2}7}) \approx O(n^{2.807})</math>. Алгоритм Штрассена є складнішим та має нижчу [[Числова стійкість|чисельну стійкість]] у порівнянні з наївним алгоритмом,<ref>{{Citation | last1=Miller | first1=Webb | title=Computational complexity and numerical stability | citeseerx = 10.1.1.148.9947 | year=1975 | journal=SIAM News | volume=4 | pages=97–107}} {{ref-en}}</ref> але він є швидшим у випадках, коли {{math|''n'' > 100}} або близько того,<ref name="skiena"/> і зустрічається в декількох бібліотеках, таких як [[Basic Linear Algebra Subprograms|''BLAS'']].<ref>{{cite book |last1=Press |first1=William H. |last2=Flannery |first2=Brian P. |last3=Teukolsky |first3=Saul A. |author3-link=Саул Тьюколски |last4=Vetterling |first4=William T. |title=[[Numerical Recipes: The Art of Scientific Computing]] |publisher=[[Cambridge University Press]] |edition=3rd |isbn=978-0-521-88068-8 |year=2007}} {{ref-en}}</ref> Він є дуже корисним для великих матриць над точними областями, такими як [[Скінченне поле|скінченні поля]], де чисельна стійкість не є проблемою.

Поточний алгоритм {{math|''O''(''n''<sup>''k''</sup>)}} з найнижчим відомим степенем {{mvar|k}} є узагальненнями [[Алгоритм Копперсміта — Вінограда|алгоритму Копперсміта — Вінограда]] від Франсуа ле Ґалля, яке має асимптотичну складність {{math|''O''(''n''<sup>2.3728639</sup>)}}.<ref>{{Citation | last1=Le Gall | first1=François | contribution=Powers of tensors and fast matrix multiplication | year = 2014 | arxiv=1401.7714 | title = Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014)| bibcode=2014arXiv1401.7714L }} {{ref-en}}. Первинний алгоритм, представлений [[Дон Копперсміт|Доном Копперсмітом]] та {{нп|Шмуель Віноград|Шмуелем Віноградом||Shmuel Winograd}} 1990 року, має асимптотичну складність {{math|''O''(''n''<sup>2.376</sup>)}}. Його було поліпшено 2013 року до {{math|''O''(''n''<sup>2.3729</sup>)}} {{нп|Вірджинія Василевська-Вільямс|Вірджинією Василевською-Вільямс||Virginia Vassilevska Williams}}, що дало тривалість лише трошки гіршу, ніж у вдосконалення ле Ґалля: {{cite web |url=http://www.cs.stanford.edu/~virgi/matrixmult-f.pdf |title=Multiplying matrices faster than Coppersmith-Winograd |first=Virginia Vassilevska |last=Williams |authorlink=Вірджинія Василевська-Вільямс |accessdate=15 грудня 2019 |archive-date=8 жовтня 2013 |archive-url=https://web.archive.org/web/20131008063524/http://www.cs.stanford.edu/~virgi/matrixmult-f.pdf }} {{Webarchive|url=https://web.archive.org/web/20131008063524/http://www.cs.stanford.edu/~virgi/matrixmult-f.pdf |date=2013-10-08 }} {{ref-en}}</ref> Алгоритм ле Ґалля та алгоритм Копперсміта — Вінограда, на якому він ґрунтується, є подібними до алгоритму Штрассена: винайдено спосіб множення двох матриць {{math|''k'' × ''k''}} менше ніж {{math|''k''<sup>3</sup>}} множеннями, і цю методику застосовують рекурсивно. Проте сталий коефіцієнт, прихований [[Нотація Ландау|нотацією Ландау]], є настільки великим, що ці алгоритми є доцільними лише для матриць, що є завеликими для обробки на сучасних комп'ютерах.<ref>{{citation
 | last = Iliopoulos
 | first = Costas S.
 | doi = 10.1137/0218045
 | issue = 4
 | journal = SIAM Journal on Computing
 | mr = 1004789
 | quote = The Coppersmith–Winograd algorithm is not practical, due to the very large hidden constant in the upper bound on the number of multiplications required.
 | pages = 658–669
 | title = Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix
 | url = http://www.williamstein.org/home/wstein/www/home/pernet/Papers/Hermite/Iliopoulos88.pdf
 | volume = 18
 | year = 1989
 | citeseerx = 10.1.1.531.9309
 | accessdate = 15 грудня 2019
 | archive-date = 5 березня 2014
 | archive-url = https://web.archive.org/web/20140305182030/http://www.williamstein.org/home/wstein/www/home/pernet/Papers/Hermite/Iliopoulos88.pdf
 }} {{Webarchive|url=https://web.archive.org/web/20140305182030/http://www.williamstein.org/home/wstein/www/home/pernet/Papers/Hermite/Iliopoulos88.pdf |date= 5 березня 2014 }} {{ref-en}}</ref><ref name="robinson">{{Cite journal | last1=Robinson | first1=Sara | title=Toward an Optimal Algorithm for Matrix Multiplication | url=https://archive.siam.org/pdf/news/174.pdf | year=2005 | journal=SIAM News | volume=38 | issue=9 | accessdate=15 грудня 2019 | archive-date=31 березня 2019 | archive-url=https://web.archive.org/web/20190331221037/https://archive.siam.org/pdf/news/174.pdf }} {{ref-en}}</ref>

Оскільки будь-який алгоритм для перемножування двох матриць {{math|''n'' × ''n''}} має обробити всі {{math|2''n''<sup>2</sup>}} елементів, існує асимптотична нижня межа в {{math|Ω(''n''<sup>2</sup>)}} операцій. Рац довів нижню межу в {{math|Ω(''n''<sup>2</sup> log(''n''))}} для арифметичних схем з обмеженими коефіцієнтами над дійсними або комплексними числами.<ref>{{нп|Ран Рац|||Ran Raz}}. On the complexity of matrix product. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM Press, 2002. {{doi|10.1145/509907.509932}}. {{ref-en}}</ref>

Кон та ін. помістили такі методи, як алгоритми Штрассена та Копперсміта — Вінограда, до зовсім відмінного контексту [[Теорія груп|теорії груп]], використавши трійки підмножин скінченних груп, які задовольняють властивості неперетинності, що називають {{нп|Властивість потрійного добутку|властивістю потрійного добутку||Triple product property}} (ВПД, {{lang-en|triple product property, TPP}}). Вони показали, що якщо сімейства {{нп|Вінковий добуток|вінкових добутків||Wreath product}} [[Абелева група|абелевих груп]] з симетричними групами втілюють сімейства трійок підмножин зі спільною версією ВПД, то існують алгоритми перемножування матриць із по суті квадратичною складністю.<ref>Henry Cohn, {{нп|Роберт Клейнберг|Robert Kleinberg||Robert Kleinberg}}, {{нп|Балаж Шегеді|Balázs Szegedy||Balázs Szegedy}}, and Chris Umans. Group-theoretic Algorithms for Matrix Multiplication. {{arxiv|math.GR/0511460}}. ''Proceedings of the 46th Annual Symposium on Foundations of Computer Science'', 23–25 October 2005, Pittsburgh, PA, IEEE Computer Society, pp.&nbsp;379–388. {{ref-en}}</ref><ref>Henry Cohn, Chris Umans. A Group-theoretic Approach to Fast Matrix Multiplication. {{arxiv|math.GR/0307321}}. ''Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science'', 11–14 October 2003, Cambridge, MA, IEEE Computer Society, pp.&nbsp;438–449. {{ref-en}}</ref> Більшість дослідників вважають, що це так і є.<ref name="robinson"/> Проте Алон, Шпілка та {{нп|Кріс Уманс|||Chris Umans}} нещодавно показали, що деякі з цих гіпотез, що передбачають швидке множення матриць, є несумісними з іншою правдоподібною гіпотезою, {{нп|Соняшникова гіпотеза|соняшниковою||Sunflower conjecture}}.<ref>[[Нога Алон|Alon]], Shpilka, Umans, [http://eccc.hpi-web.de/report/2011/067/ On Sunflowers and Matrix Multiplication] {{Webarchive|url=https://web.archive.org/web/20161209145608/http://eccc.hpi-web.de/report/2011/067/ |date=9 грудня 2016 }} {{ref-en}}</ref>

{{нп|Алгоритм Фрейвальдса|||Freivalds' algorithm}} є простим [[Алгоритм Монте-Карло|алгоритмом Монте-Карло]], який для заданих матриць {{mvar|A}}, {{mvar|B}} та {{mvar|C}} перевіряє за час {{math|Θ(''n''<sup>2</sup>)}}, чи {{math|''AB'' {{=}} ''C''}}.

== Паралельні та розподілені алгоритми ==

=== Розпаралелювання зі спільною пам'яттю ===

Окреслений вище [[#Алгоритм «розділюй та володарюй»|алгоритм «розділюй та володарюй»]] можливо [[Паралельний алгоритм|розпаралелити]] для [[Спільна пам'ять|багатопроцесорності зі спільною пам'яттю]] двома способами. Вони ґрунтуються на тім факті, що вісім рекурсивних перемножувань матриць у

: <math>\begin{pmatrix}
A_{11} B_{11} + A_{12} B_{21} & A_{11} B_{12} + A_{12} B_{22}\\
A_{21} B_{11} + A_{22} B_{21} & A_{21} B_{12} + A_{22} B_{22}\\
\end{pmatrix}
</math>

можливо виконувати незалежно одне від одного, як і чотири підсумовування (хоча алгоритмові потрібно «об'єднати» перемножування перед виконанням додавань). Використовуючи повну паралельність задачі, отримують алгоритм, який може бути виражено [[псевдокод]]ом стилю {{нп|Модель відгалужування-об'єднування|відгалужування-об'єднування||Fork–join model}}:<ref name="cilk"/>

<div style="margin-left: 35px; width: 600px">
{{framebox|blue}}
'''Процедура''' {{math|перемножити(''C'', ''A'', ''B'')}}:

* Базовий випадок: якщо {{math|''n'' {{=}} 1}}, встановити {{math|''c''<sub>11</sub> ← ''a''<sub>11</sub> × ''b''<sub>11</sub>}} (або перемножити маленьку блокову матрицю).
* Інакше, виділити простір для нової матриці {{mvar|T}} форми {{math|''n'' × ''n''}}, а тоді:
** Розбити {{mvar|A}} на {{math|''A''<sub>11</sub>}}, {{math|''A''<sub>12</sub>}}, {{math|''A''<sub>21</sub>}}, {{math|''A''<sub>22</sub>}}.
** Розбити {{mvar|B}} на {{math|''B''<sub>11</sub>}}, {{math|''B''<sub>12</sub>}}, {{math|''B''<sub>21</sub>}}, {{math|''B''<sub>22</sub>}}.
** Розбити {{mvar|C}} на {{math|''C''<sub>11</sub>}}, {{math|''C''<sub>12</sub>}}, {{math|''C''<sub>21</sub>}}, {{math|''C''<sub>22</sub>}}.
** Розбити {{mvar|T}} на {{math|''T''<sub>11</sub>}}, {{math|''T''<sub>12</sub>}}, {{math|''T''<sub>21</sub>}}, {{math|''T''<sub>22</sub>}}.
** Паралельне виконання:
*** ''Відгалузити'' {{math|перемножити(''C''<sub>11</sub>, ''A''<sub>11</sub>, ''B''<sub>11</sub>)}}.
*** ''Відгалузити'' {{math|перемножити(''C''<sub>12</sub>, ''A''<sub>11</sub>, ''B''<sub>12</sub>)}}.
*** ''Відгалузити'' {{math|перемножити(''C''<sub>21</sub>, ''A''<sub>21</sub>, ''B''<sub>11</sub>)}}.
*** ''Відгалузити'' {{math|перемножити(''C''<sub>22</sub>, ''A''<sub>21</sub>, ''B''<sub>12</sub>)}}.
*** ''Відгалузити'' {{math|перемножити(''T''<sub>11</sub>, ''A''<sub>12</sub>, ''B''<sub>21</sub>)}}.
*** ''Відгалузити'' {{math|перемножити(''T''<sub>12</sub>, ''A''<sub>12</sub>, ''B''<sub>22</sub>)}}.
*** ''Відгалузити'' {{math|перемножити(''T''<sub>21</sub>, ''A''<sub>22</sub>, ''B''<sub>21</sub>)}}.
*** ''Відгалузити'' {{math|перемножити(''T''<sub>22</sub>, ''A''<sub>22</sub>, ''B''<sub>22</sub>)}}.
** ''Об'єднати'' (дочекатися завершення паралельних відгалужень).
** {{math|додати(''C'', ''T'')}}.
** Звільнити {{mvar|T}}.

'''Процедура''' {{math|додати(''C'', ''T'')}} додає {{mvar|T}} до {{mvar|C}}, поелементно:

* Базовий випадок: якщо {{math|''n'' {{=}} 1}}, встановити {{math|''c''<sub>11</sub> ← ''c''<sub>11</sub> + ''t''<sub>11</sub>}} (або виконати короткий цикл, можливо, [[Розмотування циклу|розмотаний]]).
* Інакше:
** Розбити {{mvar|C}} на {{math|''C''<sub>11</sub>}}, {{math|''C''<sub>12</sub>}}, {{math|''C''<sub>21</sub>}}, {{math|''C''<sub>22</sub>}}.
** Розбити {{mvar|T}} на {{math|''T''<sub>11</sub>}}, {{math|''T''<sub>12</sub>}}, {{math|''T''<sub>21</sub>}}, {{math|''T''<sub>22</sub>}}.
** Паралельно:
*** ''Відгалузити'' {{math|додати(''C''<sub>11</sub>, ''T''<sub>11</sub>)}}.
*** ''Відгалузити'' {{math|додати(''C''<sub>12</sub>, ''T''<sub>12</sub>)}}.
*** ''Відгалузити'' {{math|додати(''C''<sub>21</sub>, ''T''<sub>21</sub>)}}.
*** ''Відгалузити'' {{math|додати(''C''<sub>22</sub>, ''T''<sub>22</sub>)}}.
** ''Об'єднати''.
{{frame-footer}}
</div>

Тут ''відгалузити'' є ключовим словом, яке сигналізує, що обчислення може бути виконувано паралельно до решти виклику функції, тоді як ''об'єднати'' чекає на завершення всіх попередньо «відгалужених» обчислень. {{math|Розбити}} досягає своєї мети лише маніпулюванням вказівниками.

Цей алгоритм має [[Критична довжина шляху|критичною довжиною шляху]] {{math|Θ(log<sup>2</sup> ''n'')}} кроків, що означає, що йому потрібно стільки часу на ідеальній машині з нескінченним числом процесорів. Отже, на будь-якому реальному комп'ютері він має максимальне можливе [[Прискорення (комп'ютерна архітектура)|прискорення]] {{math|Θ(''n''<sup>3</sup>/log<sup>2</sup> ''n'')}}. Цей алгоритм не є практичним через витрати на передавання, властиві переміщуванню даних до та з тимчасової матриці {{mvar|T}}, але практичніший варіант досягає прискорення {{math|Θ(''n''<sup>2</sup>)}} без використання тимчасової матриці.<ref name="cilk">{{cite thesis |type=Ph.D. |last=Randall |first=Keith H. |title=Cilk: Efficient Multithreaded Computing |publisher=Massachusetts Institute of Technology |year=1998 |pages=54–57 |url=http://supertech.csail.mit.edu/papers/randall-phdthesis.pdf |accessdate=15 грудня 2019 |archive-date=6 листопада 2020 |archive-url=https://web.archive.org/web/20201106232735/http://supertech.csail.mit.edu/papers/randall-phdthesis.pdf }} {{ref-en}}</ref>

[[Файл:Block matrix multiplication.svg|thumb|Блокове перемножування матриць. У двовимірному алгоритмі кожен із процесорів є відповідальним за одну підматрицю {{mvar|C}}. У тривимірному алгоритмі кожну з пар перемножуваних підматриць з {{mvar|A}} та {{mvar|B}} призначають одному процесорові.]]

=== Алгоритми з униканням передавання, та розподілені алгоритми ===

На сучасних архітектурах з ієрархічною пам'яттю вартість завантажування та зберігання елементів матриць входу має схильність переважати над вартістю арифметики. На одній машині це&nbsp;— кількість даних, передаваних між оперативною пам'яттю та кешем, тоді як на багатовузловій машині з розподіленою пам'яттю це&nbsp;— кількість, що передається між вузлами. В кожному з випадків її називають ''пропускною здатністю обміну'' ({{lang-en|communication bandwidth}}). Наївний алгоритм із використанням трьох вкладених циклів використовує пропускну здатністю обміну {{math|Ω(''n''<sup>3</sup>)}}.

{{нп|Алгоритм Кеннона|||Cannon's algorithm}}, відомий також як ''двовимірний алгоритм'' ({{lang-en|2D algorithm}}), є {{нп|Алгоритм з униканням обміну|алгоритмом з униканням обміну||Communication-avoiding algorithms}}, який розбиває кожну з матриць входу на блокову матрицю, чиї елементи є підматрицями розміру {{math|{{sqrt|''M''/3}}}} на {{math|{{sqrt|''M''/3}}}}, де {{math|''M''}} є розміром швидкої пам'яті.<ref>Lynn Elliot Cannon, ''[http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=905686 A cellular computer to implement the Kalman Filter Algorithm]'', Technical report, Ph.D. Thesis, Montana State University, 14 July 1969. {{ref-en}}</ref> Потім застосовують наївний алгоритм над блоковими матрицями, обчислюючи добутки підматриць цілком у швидкій пам'яті. Це знижує пропускну здатність обміну до {{math|''O''(''n''<sup>3</sup>/{{sqrt|''M''}})}}, яка є асимптотично оптимальною (для алгоритмів, що виконують обчислення {{math|Ω(''n''<sup>3</sup>)}}).<ref>{{cite journal|last=Hong|first=J. W.|first2=H. T.|last2=Kung|title=I/O complexity: The red-blue pebble game|journal=STOC '81: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing|year=1981|pages=326–333|url=https://apps.dtic.mil/dtic/tr/fulltext/u2/a104739.pdf|accessdate=15 грудня 2019|archive-date=15 грудня 2019|archive-url=https://web.archive.org/web/20191215182754/https://apps.dtic.mil/dtic/tr/fulltext/u2/a104739.pdf}} {{Webarchive|url=https://web.archive.org/web/20191215182754/https://apps.dtic.mil/dtic/tr/fulltext/u2/a104739.pdf |date=2019-12-15 }} {{ref-en}}</ref><ref name=irony>{{cite journal|last=Irony|first=Dror|first2=Sivan |last2=Toledo |first3=Alexander |last3=Tiskin |title=Communication lower bounds for distributed-memory matrix multiplication|journal=J. Parallel Distrib. Comput.|date=September 2004|volume=64|issue=9|pages=1017–1026|doi=10.1016/j.jpdc.2004.03.021|citeseerx=10.1.1.20.7034}} {{ref-en}}</ref>

У розподіленій постановці з {{mvar|p}} процесорами, розставленими у двовимірній сітці {{math|{{sqrt|''p''}}}} на {{math|{{sqrt|''p''}}}}, кожному з процесорів можливо призначувати по одній з підматриць результату, і добуток буде обчислювано з передаванням кожним з процесорів {{math|''O''(''n''<sup>2</sup>/{{sqrt|''p''}})}} слів, що є асимптотично оптимальним, виходячи з того, що кожен з вузлів зберігає щонайменше {{math|''O''(''n''<sup>2</sup>/''p'')}} елементів.<ref name=irony/> Це може бути вдосконалено ''тривимірним алгоритмом'' ({{lang-en|3D algorithm}}), який впорядковує процесори у тривимірну кубічну сітку, призначуючи кожен добуток двох підматриць входу одному процесорові. Підматриці результату потім породжують виконанням зведення над кожним з рядків.<ref name="Agarwal">{{cite journal|last=Agarwal|first=R.C.|first2=S. M. |last2=Balle |first3=F. G. |last3=Gustavson |first4=M. |last4=Joshi |first5=P. |last5=Palkar |title=A three-dimensional approach to parallel matrix multiplication|journal=IBM J. Res. Dev.|date=September 1995|volume=39|issue=5|pages=575–582|doi=10.1147/rd.395.0575|citeseerx=10.1.1.44.3404}} {{ref-en}}</ref> Цей алгоритм передає {{math|''O''(''n''<sup>2</sup>/''p''<sup>2/3</sup>)}} слів на процесор, що є асимптотично оптимальним.<ref name=irony/> Проте, це вимагає повторювання кожного з елементів матриць входу {{math|''p''<sup>1/3</sup>}} разів, і відтак вимагає в {{math|''p''<sup>1/3</sup>}} разів більше пам'яті, ніж необхідно для зберігання входів. Для подальшого зниження тривалості виконання цей алгоритм може бути поєднувано з алгоритмом Штрассена.<ref name="Agarwal"/> ''«2,5-вимірні»'' алгоритми ({{lang-en|"2.5D" algorithms}}) забезпечують безперервний компроміс між використанням пам'яті та пропускною здатністю передавання.<ref>{{cite journal|last=Solomonik|first=Edgar|first2=James |last2=Demmel|title=Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms|journal=Proceedings of the 17th International Conference on Parallel Processing|year=2011|volume=Part II|pages=90–109}} {{ref-en}}</ref> На сучасних розподілених обчислювальних середовищах, таких як [[MapReduce]], було розроблено спеціалізовані алгоритми перемножування.<ref>{{cite journal|last1=Bosagh Zadeh|first1=Reza|last2=Carlsson|first2=Gunnar|title=Dimension Independent Matrix Square Using MapReduce|url=http://stanford.edu/~rezab/papers/dimsum.pdf|accessdate=12 липня 2014|journal=|archive-date=14 липня 2014|archive-url=https://web.archive.org/web/20140714214640/http://stanford.edu/~rezab/papers/dimsum.pdf}} {{ref-en}}</ref>

=== Алгоритми для сіток ===
[[Файл:Matrix multiplication on a cross-wire two-dimensional array.png|thumb|240px|Матричне перемножування, виконане за 2n-1 кроків для двох матриць n×n на перехрещуваній сітці.]]

Існує низка алгоритмів для перемножування на [[Сіткова мережа|сітках]]. Для перемножування двох ''n''×''n'' на стандартній двовимірній сітці із застосуванням двовимірного {{нп|Алгоритм Кеннона|алгоритму Кеннона||Cannon's algorithm}} обчислюють перемножування в 3''n''-2 кроків, хоча це знижується до половини цього числа для повторюваних обчислень.<ref>Bae, S.E., T.-W. Shinn, T. Takaoka (2014) [https://www.sciencedirect.com/science/article/pii/S1877050914003858/pdf?md5=4d641ad288db14733fb2f82ee445c258&pid=1-s2.0-S1877050914003858-main.pdf&_valck=1 A faster parallel algorithm for matrix multiplication on a mesh array] {{Webarchive|url=https://web.archive.org/web/20210518032449/https://www.sciencedirect.com/science/article/pii/S1877050914003858/pdf?md5=4d641ad288db14733fb2f82ee445c258&pid=1-s2.0-S1877050914003858-main.pdf&_valck=1 |date=18 травня 2021 }}. Procedia Computer Science 29: 2230-2240 {{ref-en}}</ref> Стандартний масив є неефективним, оскільки дані з двох матриць не надходять одночасно, і його має бути доповнювано нулями.

Результат є ще швидшим на двошаровій перехрещуваній сітці, де потрібно лише 2''n''-1 кроків.<ref>Kak, S. (1988) [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.8527&rep=rep1&type=pdf A two-layered mesh array for matrix multiplication]. Parallel Computing 6: 383-385 {{ref-en}}</ref> Продуктивність додатково покращується для повторюваних обчислень, ведучи до стовідсоткової ефективності.<ref>Kak, S. (2014) Efficiency of matrix multiplication on the cross-wired mesh array. https://arxiv.org/abs/1411.3273 {{Webarchive|url=https://web.archive.org/web/20190323193939/https://arxiv.org/abs/1411.3273 |date=23 березня 2019 }} {{ref-en}}</ref> Перехрещуваний сітковий масив можна розглядати як особливий випадок не планарної (тобто, багатошарової) оброблювальної структури.<ref>Kak, S. (1988) [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.4753&rep=rep1&type=pdf Multilayered array computing]. Information Sciences 45: 347-365 {{ref-en}}</ref>

== Див. також ==

* {{нп|Обчислювальна складність математичних операцій|||Computational complexity of mathematical operations}}
* {{нп|Алгоритм Велієнта|Алгоритм КЯК, § Алгоритм Велієнта||Valiant's algorithm}}
* {{нп|Задача про порядок перемножування матриць|||Matrix chain multiplication}}
* {{нп|Розріджене матрично-векторне множення|||Sparse matrix-vector multiplication}}

== Примітки ==

{{reflist|30em}}

== Література ==

* {{Cite journal| doi = 10.1016/j.parco.2008.10.002| title = A class of parallel tiled linear algebra algorithms for multicore architectures| journal = Parallel Computing| volume = 35| pages = 38–53| year = 2009| last1 = Buttari | first1 = Alfredo| last2 = Langou | first2 = Julien| last3 = Kurzak | first3 = Jakub| last4 = Dongarra | first4 = Jack |authorlink4=Джек Донґарра| arxiv = 0709.1272}} {{ref-en}}
* {{Cite journal | doi = 10.1145/1356052.1356053| title = Anatomy of high-performance matrix multiplication| journal = ACM Transactions on Mathematical Software| volume = 34| issue = 3| pages =1–25| year = 2008| last1 = Goto | first1 = Kazushige| last2 = van de Geijn | first2 = Robert A.| citeseerx = 10.1.1.140.3583}} {{ref-en}}
* {{Cite journal | doi = 10.1145/2764454 | title = BLIS: A Framework for Rapidly Instantiating BLAS Functionality| journal = ACM Transactions on Mathematical Software| volume = 41| issue = 3| pages =1–33| year = 2015| last1 = Van Zee  | first1 = Field G.| last2 = van de Geijn | first2 = Robert A.}} {{ref-en}}
* [https://github.com/flame/how-to-optimize-gemm How To Optimize GEMM] {{Webarchive|url=https://web.archive.org/web/20200915062912/https://github.com/flame/how-to-optimize-gemm |date=15 вересня 2020 }} {{ref-en}}

{{Числова лінійна алгебра}}

[[Категорія:Алгоритми множення матриць| ]]