Алгоритм перемножування матриць

Шаблон:Short description Шаблон:Нерозв'язано Оскільки множення матриць є настільки центральною операцією в багатьох чисельних алгоритмах, у те, щоби зробити алгори́тми перемно́жування ма́триць ефективними, було вкладено чимало праці. Застосування множення матриць в обчислювальних задачах зустрічаються в багатьох областях, включно з Шаблон:Нп та розпізнаванням образів, і в, здавалося би, не пов'язаних задачах, таких як підрахунок шляхів графом. Було розроблено багато різних алгоритмів для перемножування матриць на різних типах апаратного забезпечення, включно з паралельними та розподіленими системами, де обчислювальну працю розподілювано декількома процесорами (можливо, через мережу).

Безпосереднє застосування математичного означення множення матриць дає алгоритм, що для перемножування двох матриць Шаблон:Math займає часу порядку Шаблон:Math (в нотації Ландау — Шаблон:Math). Кращі асимптотичні межі часу, необхідного для перемножування матриць, були відомі від часів праці Страссена 1960 року, але досі не відомо, яким є оптимальний час (тобто, якою є складність цієї задачі).

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

За означенням множення матриць, якщо Шаблон:Math для матриці Шаблон:Mvar розміру Шаблон:Math та матриці Шаблон:Mvar розміру Шаблон:Math, то Шаблон:Mvar є матрицею розміру Шаблон:Math з елементами

$c_{ij}=\sum _{k=1}^m{a}_{ik}{b}_{kj}$.

З цього може бути побудовано простий алгоритм, який обходить циклами індекси Шаблон:Mvar з 1 по Шаблон:Mvar та Шаблон:Mvar з 1 по Шаблон:Mvar, обчислюючи наведене вище із застосуванням вкладеного циклу:

• Вхід: матриці Шаблон:Mvar та Шаблон:Mvar
• Нехай Шаблон:Mvar буде матрицею відповідного розміру
• Для Шаблон:Mvar з 1 по Шаблон:Mvar:
  • Для Шаблон:Mvar з 1 по Шаблон:Mvar:
    • Нехай Шаблон:Math
    • Для Шаблон:Mvar з 1 по Шаблон:Mvar:
      • Встановити Шаблон:Math
    • Встановити Шаблон:Math
• Повернути Шаблон:Mvar

Цей алгоритм займає час Шаблон:Math (в нотації Ландау). Поширеним спрощенням для цілей аналізу алгоритмів є вважати, що всі входи є квадратними матрицями розміру Шаблон:Math, в разі чого час виконання становить Шаблон:Math, тобто, є кубічним.

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

Ілюстрація порядко́вого та постовпчикового порядку

Ці три цикли в ітеративному перемножуванні матриць можливо довільно переставляти між собою без впливу на правильність чи асимптотичну тривалість виконання. Проте цей порядок може мати значний вплив на практичну продуктивність через Шаблон:Нп алгоритму та використання ним кешу; який порядок є кращим також залежить від того, чи зберігаються матриці в Шаблон:Нп, постовпчиковому, чи суміші обох.

Зокрема, в ідеалізованому випадку повністю асоціативного кешу, складеного з Шаблон:Mvar байтів та Шаблон:Mvar байтів на рядок кешу (тобто, Шаблон:Sfrac рядків кешу), наведений вище алгоритм є недооптимальним для Шаблон:Mvar та Шаблон:Mvar, що зберігаються в порядко́вому порядку. Коли Шаблон:Math, кожна ітерація внутрішнього циклу (одночасного проходження рядком Шаблон:Mvar та стовпчиком Шаблон:Mvar) зазнає́ невлучання в кеш при отримуванні доступу до елементу Шаблон:Mvar. Це означає, що цей алгоритм у найгіршому випадку зазнає Шаблон:Math невлучань у кеш. Шаблон:As of рік швидкість пам'яті в порівнянні зі швидкістю процесорів є такою, що для матриць значного розміру в тривалості виконання домінують невлучання в кеш, а не фактичні обчислення.

Оптимальним варіантом ітеративного алгоритму для Шаблон:Mvar та Шаблон:Mvar, що зберігаються в порядку рядків, є Шаблон:Нп версія, в якій матрицю неявно ділять на квадратні плитки розміру Шаблон:Math на Шаблон:Math:

• Вхід: матриці Шаблон:Mvar та Шаблон:Mvar
• Нехай Шаблон:Mvar буде матрицею відповідного розміру
• Обрати розмір плитки Шаблон:Math
• Для Шаблон:Mvar з 1 по Шаблон:Mvar кроками по Шаблон:Mvar:
  • Для Шаблон:Mvar з 1 по Шаблон:Mvar кроками по Шаблон:Mvar:
    • Для Шаблон:Mvar з 1 по Шаблон:Mvar кроками по Шаблон:Mvar:
      • Перемножити Шаблон:Math та Шаблон:Math до Шаблон:Math, тобто:
      • Для Шаблон:Mvar з Шаблон:Mvar по Шаблон:Math:
        • Для Шаблон:Mvar з Шаблон:Mvar по Шаблон:Math:
          • Нехай Шаблон:Math
          • Для Шаблон:Mvar з Шаблон:Mvar по Шаблон:Math:
            • Встановити Шаблон:Math
          • Встановити Шаблон:Math
• Повернути Шаблон:Mvar

В ідеалізованій моделі кешу цей алгоритм зазнає лише Шаблон:Math невлучань у кеш; дільник Шаблон:Math становить декілька порядків на сучасних машинах, тож у тривалості виконання домінують фактичні обчислення, а не невлучання в кеш.

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

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

$C=\left(\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right),A=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right),B=\left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right)$,

яке працює для всіх квадратних матриць, чиї розміри є степенями двійки, тобто, форми Шаблон:Math для деякого Шаблон:Mvar. Тепер добутком матриць є

$\left(\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right)=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right)\left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right)=\left(\begin{array}{cc}{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{array}\right)$

що складається з восьми множень пар підматриць, з подальшим кроком додавання. Алгоритм «розділюй та володарюй» обчислює менші добутки рекурсивно, застосовуючи як основу скалярне множення Шаблон:Math.

Складність цього алгоритму як функції від Шаблон:Mvar задається рекурентно як

$T(1)=\mathrm{\Theta }(1)$;

$T(n)=8T(n/2)+\mathrm{\Theta }(n^2)$,

із враховуванням восьми рекурсивних викликів на матрицях розміру Шаблон:Math, та Шаблон:Math для поелементного підсумовування чотирьох пар отримуваних в результаті матриць. Застосування майстер-методу для рекурсій «розділюй та володарюй» показує, що ця рекурсія має розв'язок Шаблон:Math, такий же, як й ітеративний алгоритм.

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

Варіант цього алгоритму, який працює для матриць довільних форм, і є швидшим на практиці, розбиває матриці на дві замість чотирьох підматриць наступним чином. Розбивання матриці тепер означає поділ її на дві частини рівного розміру, або якомога ближче до рівних розмірів у разі, якщо розміри є непарними.

• Входи: матриці Шаблон:Mvar розміру Шаблон:Math, Шаблон:Mvar розміру Шаблон:Math.
• Базовий випадок: якщо Шаблон:Math є нижчим за певний поріг, застосувати розмотану версію ітеративного алгоритму.
• Рекурсивні випадки:

• Якщо Шаблон:Math, розбити Шаблон:Mvar горизонтально:

$C=\left(\begin{array}{c}{A}_1\\ A_2\end{array}\right)B=\left(\begin{array}{c}{A}_{1}B\\ A_{2}B\end{array}\right)$

• Інакше, якщо Шаблон:Math, розбити Шаблон:Mvar вертикально:

$C=A\left(\begin{array}{cc}{B}_1& B_2\end{array}\right)=\left(\begin{array}{cc}A{B}_1& A{B}_2\end{array}\right)$

• Інакше, Шаблон:Math. Робити Шаблон:Mvar вертикально та Шаблон:Mvar горизонтально:

$C=\left(\begin{array}{cc}{A}_1& A_2\end{array}\right)\left(\begin{array}{c}{B}_1\\ B_2\end{array}\right)=A_1{B}_1+A_2{B}_2$

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

Рівень невлучання в кеш в рекурсивного матричного множення є таким же, як і в Шаблон:Нп ітеративної версії, але, на відміну від того алгоритму, рекурсивний алгоритм є Шаблон:Нп: він не має параметру налаштування, необхідного для досягнення оптимальної продуктивності кешу, і він добре поводиться в Шаблон:Нп середовищі, де розміри кешу є фактично динамічними через те, що інші процеси займають його простір. (Простий ітеративний алгоритм також є буферо-незалежним, але набагато повільнішим на практиці, якщо компонування матриць не пристосовано до алгоритму.)

Кількість невлучань у кеш, що зазнає́ цей алгоритм на машині з Шаблон:Mvar рядками ідеально кешу розміру Шаблон:Mvar байтів кожен, обмеженоШаблон:RШаблон:Rp

$\mathrm{\Theta }(m+n+p+\frac{mn+np+mp}{b}+\frac{mnp}{b\sqrt{M}})$

Підкубічні алгоритми

Найнижче Шаблон:Mvar, таке, що відомо, що множення матриць є в Шаблон:Math, відображене за часом.

Існують алгоритми, що забезпечують кращу тривалість виконання, ніж прямолінійні. Першим було відкрито алгоритм Штрассена, винайдений Фолькером Штрассеном 1969 року, який часто називають «швидким множенням матриць» (Шаблон:Lang-en). Він ґрунтується на способі множення двох матриць Шаблон:Math, який вимагає лише 7 множень (замість звичайних 8), ціною декількох додаткових операції додавання та віднімання. Його рекурсивне застосування дає алгоритм з витратами на множення $O(n^{{\log }_{2}7})\approx O(n^{2.807})$. Алгоритм Штрассена є складнішим та має нижчу чисельну стійкість у порівнянні з наївним алгоритмом, але він є швидшим у випадках, коли Шаблон:Math або близько того, і зустрічається в декількох бібліотеках, таких як BLAS. Він є дуже корисним для великих матриць над точними областями, такими як скінченні поля, де чисельна стійкість не є проблемою.

Поточний алгоритм Шаблон:Math з найнижчим відомим степенем Шаблон:Mvar є узагальненнями алгоритму Копперсміта — Вінограда від Франсуа ле Ґалля, яке має асимптотичну складність Шаблон:Math. Алгоритм ле Ґалля та алгоритм Копперсміта — Вінограда, на якому він ґрунтується, є подібними до алгоритму Штрассена: винайдено спосіб множення двох матриць Шаблон:Math менше ніж Шаблон:Math множеннями, і цю методику застосовують рекурсивно. Проте сталий коефіцієнт, прихований нотацією Ландау, є настільки великим, що ці алгоритми є доцільними лише для матриць, що є завеликими для обробки на сучасних комп'ютерах.

Оскільки будь-який алгоритм для перемножування двох матриць Шаблон:Math має обробити всі Шаблон:Math елементів, існує асимптотична нижня межа в Шаблон:Math операцій. Рац довів нижню межу в Шаблон:Math для арифметичних схем з обмеженими коефіцієнтами над дійсними або комплексними числами.

Кон та ін. помістили такі методи, як алгоритми Штрассена та Копперсміта — Вінограда, до зовсім відмінного контексту теорії груп, використавши трійки підмножин скінченних груп, які задовольняють властивості неперетинності, що називають Шаблон:Нп (ВПД, Шаблон:Lang-en). Вони показали, що якщо сімейства Шаблон:Нп абелевих груп з симетричними групами втілюють сімейства трійок підмножин зі спільною версією ВПД, то існують алгоритми перемножування матриць із по суті квадратичною складністю. Більшість дослідників вважають, що це так і є. Проте Алон, Шпілка та Шаблон:Нп нещодавно показали, що деякі з цих гіпотез, що передбачають швидке множення матриць, є несумісними з іншою правдоподібною гіпотезою, Шаблон:Нп.

Шаблон:Нп є простим алгоритмом Монте-Карло, який для заданих матриць Шаблон:Mvar, Шаблон:Mvar та Шаблон:Mvar перевіряє за час Шаблон:Math, чи Шаблон:Math.

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

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

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

$\left(\begin{array}{cc}{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{array}\right)$

можливо виконувати незалежно одне від одного, як і чотири підсумовування (хоча алгоритмові потрібно «об'єднати» перемножування перед виконанням додавань). Використовуючи повну паралельність задачі, отримують алгоритм, який може бути виражено псевдокодом стилю Шаблон:Нп:

Шаблон:Framebox Процедура Шаблон:Math:

• Базовий випадок: якщо Шаблон:Math, встановити Шаблон:Math (або перемножити маленьку блокову матрицю).
• Інакше, виділити простір для нової матриці Шаблон:Mvar форми Шаблон:Math, а тоді:
  • Розбити Шаблон:Mvar на Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math.
  • Розбити Шаблон:Mvar на Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math.
  • Розбити Шаблон:Mvar на Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math.
  • Розбити Шаблон:Mvar на Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math.
  • Паралельне виконання:
    • Відгалузити Шаблон:Math.
    • Відгалузити Шаблон:Math.
    • Відгалузити Шаблон:Math.
    • Відгалузити Шаблон:Math.
    • Відгалузити Шаблон:Math.
    • Відгалузити Шаблон:Math.
    • Відгалузити Шаблон:Math.
    • Відгалузити Шаблон:Math.
  • Об'єднати (дочекатися завершення паралельних відгалужень).
  • Шаблон:Math.
  • Звільнити Шаблон:Mvar.

Процедура Шаблон:Math додає Шаблон:Mvar до Шаблон:Mvar, поелементно:

• Базовий випадок: якщо Шаблон:Math, встановити Шаблон:Math (або виконати короткий цикл, можливо, розмотаний).
• Інакше:
  • Розбити Шаблон:Mvar на Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math.
  • Розбити Шаблон:Mvar на Шаблон:Math, Шаблон:Math, Шаблон:Math, Шаблон:Math.
  • Паралельно:
    • Відгалузити Шаблон:Math.
    • Відгалузити Шаблон:Math.
    • Відгалузити Шаблон:Math.
    • Відгалузити Шаблон:Math.
  • Об'єднати.

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

Цей алгоритм має критичною довжиною шляху Шаблон:Math кроків, що означає, що йому потрібно стільки часу на ідеальній машині з нескінченним числом процесорів. Отже, на будь-якому реальному комп'ютері він має максимальне можливе прискорення Шаблон:Math. Цей алгоритм не є практичним через витрати на передавання, властиві переміщуванню даних до та з тимчасової матриці Шаблон:Mvar, але практичніший варіант досягає прискорення Шаблон:Math без використання тимчасової матриці.

Блокове перемножування матриць. У двовимірному алгоритмі кожен із процесорів є відповідальним за одну підматрицю Шаблон:Mvar. У тривимірному алгоритмі кожну з пар перемножуваних підматриць з Шаблон:Mvar та Шаблон:Mvar призначають одному процесорові.

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

На сучасних архітектурах з ієрархічною пам'яттю вартість завантажування та зберігання елементів матриць входу має схильність переважати над вартістю арифметики. На одній машині це — кількість даних, передаваних між оперативною пам'яттю та кешем, тоді як на багатовузловій машині з розподіленою пам'яттю це — кількість, що передається між вузлами. В кожному з випадків її називають пропускною здатністю обміну (Шаблон:Lang-en). Наївний алгоритм із використанням трьох вкладених циклів використовує пропускну здатністю обміну Шаблон:Math.

Шаблон:Нп, відомий також як двовимірний алгоритм (Шаблон:Lang-en), є Шаблон:Нп, який розбиває кожну з матриць входу на блокову матрицю, чиї елементи є підматрицями розміру Шаблон:Math на Шаблон:Math, де Шаблон:Math є розміром швидкої пам'яті. Потім застосовують наївний алгоритм над блоковими матрицями, обчислюючи добутки підматриць цілком у швидкій пам'яті. Це знижує пропускну здатність обміну до Шаблон:Math, яка є асимптотично оптимальною (для алгоритмів, що виконують обчислення Шаблон:Math).

У розподіленій постановці з Шаблон:Mvar процесорами, розставленими у двовимірній сітці Шаблон:Math на Шаблон:Math, кожному з процесорів можливо призначувати по одній з підматриць результату, і добуток буде обчислювано з передаванням кожним з процесорів Шаблон:Math слів, що є асимптотично оптимальним, виходячи з того, що кожен з вузлів зберігає щонайменше Шаблон:Math елементів. Це може бути вдосконалено тривимірним алгоритмом (Шаблон:Lang-en), який впорядковує процесори у тривимірну кубічну сітку, призначуючи кожен добуток двох підматриць входу одному процесорові. Підматриці результату потім породжують виконанням зведення над кожним з рядків. Цей алгоритм передає Шаблон:Math слів на процесор, що є асимптотично оптимальним. Проте, це вимагає повторювання кожного з елементів матриць входу Шаблон:Math разів, і відтак вимагає в Шаблон:Math разів більше пам'яті, ніж необхідно для зберігання входів. Для подальшого зниження тривалості виконання цей алгоритм може бути поєднувано з алгоритмом Штрассена. «2,5-вимірні» алгоритми (Шаблон:Lang-en) забезпечують безперервний компроміс між використанням пам'яті та пропускною здатністю передавання. На сучасних розподілених обчислювальних середовищах, таких як MapReduce, було розроблено спеціалізовані алгоритми перемножування.

Алгоритми для сіток

Матричне перемножування, виконане за 2n-1 кроків для двох матриць n×n на перехрещуваній сітці.

Існує низка алгоритмів для перемножування на сітках. Для перемножування двох n×n на стандартній двовимірній сітці із застосуванням двовимірного Шаблон:Нп обчислюють перемножування в 3n-2 кроків, хоча це знижується до половини цього числа для повторюваних обчислень. Стандартний масив є неефективним, оскільки дані з двох матриць не надходять одночасно, і його має бути доповнювано нулями.

Результат є ще швидшим на двошаровій перехрещуваній сітці, де потрібно лише 2n-1 кроків. Продуктивність додатково покращується для повторюваних обчислень, ведучи до стовідсоткової ефективності. Перехрещуваний сітковий масив можна розглядати як особливий випадок не планарної (тобто, багатошарової) оброблювальної структури.

Див. також

• Шаблон:Нп
• Шаблон:Нп
• Шаблон:Нп
• Шаблон:Нп

Література

• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• Шаблон:Cite journal Шаблон:Ref-en
• How To Optimize GEMM Шаблон:Webarchive Шаблон:Ref-en