Алгоритам множења матрица

Алгоритам множења матрица је опис решавања математичких операција код множења матрица.

С обзиром да је множење матрица централна операција у многим нумеричким алгоритмима, много труда је уложено у израду ефикасног алгоритма множења матрица. Примена множења матрица у рачунским проблемима може се видети у многим пољима међу којима су и научно рачунање и препознавање образаца, као и у наизглед неповезаним проблемима попут рачунања путања у графу. Многи различити алгоритми су прављени за множење матрица на различитим типовима хардвера, укључујући паралелне и дистрибуиране системе, где се процес рачунског посла одвија проширено на више процесора, нпр. преко мреже.

Директна примена математичке дефиниције множења матрица даје нам алгоритам коме је потребно времена реда $н 3$ да би помножио две $н \times н$ матрице. Боље асимптотске границе времена потребног за множење матрица позната су још од рада Штрасена у 1960-им годинама, али још увек није познато оптимално време, тј. комплексност проблема.

Проблем најбржег алгоритма за множење матрица представља један од нерешених проблема у рачунарским наукама.

Итеративни алгоритам

Дефиниција множења матрица је: ако је $C = АБ$ за $н \times м$ матрицу А и $м \times п$ матрица Б, онда је C $н \times п$ матрица са уносом:

c_{ij}=\sum _{k=1}^{m}a_{ik}b_{kj}

.

Из овога, једноставан алгоритам може бити конструисан који се понавља у петљи преко индекса и од 1 до н и ј од 1 до п, рачунајући једначину изнад користећи угњеждену петљу:

   Input: matrices A and B
   Let C be a new matrix of the appropriate size
   For i from 1 to n:
       For j from 1 to p:
           Let sum = 0
           For k from 1 to m:
               Set sum ← sum + Aik × Bkj
           Set Cij ← sum
   Return C

Овај алгоритам се извршава у $Θ(нмп)$ времену у асимптотској нотацији. Уобичајено поједностављење у циљу анализе алгоритама јесте претпоставка да су улази све квадратне матрице димензија $н \times н$ , у ком случају је време извршења $Θ(н 3)$ .

Кеш понашање

Три петље у итеративном множењу матрица могу се произвољно заменити без утицаја на тачност или асимптотско време извршења алгоритма. Међутим, ред може имати значајан утицај на практичну перформансу због образаца приступа меморији и кеш коришћења алгоритма. Који редослед је најбољи такође зависи од тога да ли се матрице чувају у редоследу прво ред, редоследу прво колона, или мешавина оба.

Конкретно, у идеалном случају потпуно асоцијативог кеша који се састоји од M кеш линија по б бајтова сваки, горепоменути алгоритам је подоптималан за А и Б који се чувају у редоследу прво ред. Када је $н > .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/M'б$ , свака итерација унутрашње петље води до промашаја кеша када се приступа реду Б. То значи да алгоритам сноси $Θ(н 3)$ кеш промашаја у најгорем случају. Од 2010. године, меморијске брзине упоређене са брзинама процесора су такве да кеш промашаји, а не стварни прорачуни, доминирају временом извршења за прилично велике матрице.

Оптимална варијанта итеративног алгоритма за А и Б у распореду прво ред је верзија са плочицама, где је матрица имплицитно подељена на квадратне плочице величине $\sqrt M$ $\sqrt M$

   Input: matrices A and B
   Let C be a new matrix of the appropriate size
   Pick a tile size T = Θ(√M)
   For I from 1 to n in steps of T:
       For J from 1 to p in steps of T:
           For K from 1 to m in steps of T:
               Multiply AI:I+T, K:K+T and BK:K+T, J:J+T into CI:I+T, J:J+T, that is:
               For i from I to min(I + T, n):
                   For j from J to min(J + T, p):
                       Let sum = 0
                       For k from K to min(K + T, m):
                           Set sum ← sum + Aik × Bkj
                       Set Cij ← sum
   Return C

У идеализованом кеш моделу, овај алгоритам сноси само Θ(н3/б √М) кеш промашаја, делилац б √М износи неколико редова величине на модерним машинама, тако да стварни прорачуни доминирају временом извршења, а не кеш промашаји.

Завади па владај алгоритам

Алтернатива итеративном алгоритму је "Завади па владај" алгоритам за множење матрица. Ово се односи на поделу блокова:

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}}

.

што ради за све квадратне матрице чије су димензије степени броја 2, нпр. облици су $2 н \times 2 н$ за неко н. Производ матрица је сад:

{\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}}

који се састоји од 8 множења парова подматрица, праћено кораком сабирања. Завади па владај алгоритам рачуна најмања множења рекурзивно, користећи скаларно множење $ц 11 = а 11 б 11$ као базни случај. Комплексност овог алгоритма у функцији од н је дат рекурзијом:

T(1)=\Theta (1)

;

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

,

рачунајуци 8 рекурзивних позива матрице велицине $н /2$ и $Θ(н 2)$ да би се сабрала 4 пара резултујућих матрица. Примена ове теореме показује да рекурзија има решење $Θ(н 3)$ као и итеративни алгоритам.

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

Варијанта овог алгоритма која ради за матрице произвољних димензија и бржа је у пракси дели матрице на две уместо на четири подматрице, као што је приказано испод. Нека су димензије матрица $н \times м$ за А и $м \times п$ за Б. Дељење матрице значи делити је на два дела једнаких величина, или што је ближе могуће у случају матрица непарних димензија.

Базни случај: ако је $маx(н, м, п)$ испод одређене границе, користити верзију одмотавања петљи итеративног алгоритма.
Рекурзивни случај:

Иф $маx(н, м, п) = н$ , поделити А хоризонтално:

C={\begin{pmatrix}A_{1}\\A_{2}\end{pmatrix}}{B}={\begin{pmatrix}A_{1}B\\A_{2}B\end{pmatrix}}

Елсе, иф $маx(н, м, п) = п$ , поделити Б вертикално:

C=A{\begin{pmatrix}B_{1}&B_{2}\end{pmatrix}}={\begin{pmatrix}AB_{1}&AB_{2}\end{pmatrix}}

Елсе, $маx(н, м, п) = м$ . Поделити А вертикално и Б хоризонтално:

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}

Кеш понашање

Степен промашаја кеша у рекурзивном множењу матрица је исти као и у итеративној верзији са плочицама, али за разлику од итеративног алгоритма, рекурзивни је несвестан кеша, што значи да нема подешавања параметара потребних да би се добила оптимална перформанса кеша, и понаша се добро у мултипрограмским окружењима, где су кеш величине ефикасно днамичне због других процеса који заузимају кеш простор. Једноставни итеративни алгоритам је такође несвестан кеша али много спорији у пракси ако распоред матрица није пролагођен алгоритму.

Број кеш промашаја у овом алгоритму на машини са M линија идеалног кеша, сваки величине б бајтова је

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

Други алгоритми за множење матрица

Подкубни алгоритам
Паралелни и дистрибуирани алгоритми

Види још

Референце

Додатна литература

Скиена, Стевен С. (2012). „Сортинг анд Сеарцхинг”. Тхе Алгоритхм Десигн Мануал. стр. 103—144. ИСБН 978-1-84800-069-8. дои:10.1007/978-1-84800-070-4_4.

Спољашње везе