Штрасенов алгоритам

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

Штрасенов алгоритам, који је добио име по немачком математичару Волкеру Штрасену, служи за множење матрица. Бржи је од стандардног алгоритма за множење матрица и користи се за матрице великог степена, међутим постоје алгоритми који су још бржи за веома велике матрице.

Историја

Волкер Штрасен је овај алгоритам објавио 1969. године и доказао да за $n 3$ стандардни алгоритам није оптималан. Штрасенов алгоритам није пуно бољи, али је проузроковао интезивније истраживање на тему множења матрица што је довело до бржих алгоритама као што је Coppersmith–Winograd алгоритам.

Алгоритам

Схематски приказ Штрасеновог алгоритма

Нека су A и B квадратне матрице над Р. Ми желимо да израчунамо њихов производ што ће бити матрица C:

\mathbf {C} =\mathbf {A} \mathbf {B} \qquad \mathbf {A} ,\mathbf {B} ,\mathbf {C} \in R^{2^{n}\times 2^{n}}

Ако A и/или B нису типа $2^{x}\times 2^{x}$ попунимо редове и колоне који недостају нулама.

Поделимо A, B и C у блокове једнаких димензија:

\mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1,1}&\mathbf {A} _{1,2}\\\mathbf {A} _{2,1}&\mathbf {A} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {B} ={\begin{bmatrix}\mathbf {B} _{1,1}&\mathbf {B} _{1,2}\\\mathbf {B} _{2,1}&\mathbf {B} _{2,2}\end{bmatrix}}{\mbox{ , }}\mathbf {C} ={\begin{bmatrix}\mathbf {C} _{1,1}&\mathbf {C} _{1,2}\\\mathbf {C} _{2,1}&\mathbf {C} _{2,2}\end{bmatrix}}

тако да важи:

\mathbf {A} _{i,j},\mathbf {B} _{i,j},\mathbf {C} _{i,j}\in R^{2^{n-1}\times 2^{n-1}}

онда је:

\mathbf {C} _{1,1}=\mathbf {A} _{1,1}\mathbf {B} _{1,1}+\mathbf {A} _{1,2}\mathbf {B} _{2,1}

\mathbf {C} _{1,2}=\mathbf {A} _{1,1}\mathbf {B} _{1,2}+\mathbf {A} _{1,2}\mathbf {B} _{2,2}

\mathbf {C} _{2,1}=\mathbf {A} _{2,1}\mathbf {B} _{1,1}+\mathbf {A} _{2,2}\mathbf {B} _{2,1}

\mathbf {C} _{2,2}=\mathbf {A} _{2,1}\mathbf {B} _{1,2}+\mathbf {A} _{2,2}\mathbf {B} _{2,2}

Овим нисмо смањили број множења. Још увек нам треба 8 множења да бисмо одредили C_i,j матрице.

Следи најважнији део. Дефинишемо нове матрице:

\mathbf {M} _{1}:=(\mathbf {A} _{1,1}+\mathbf {A} _{2,2})(\mathbf {B} _{1,1}+\mathbf {B} _{2,2})

\mathbf {M} _{2}:=(\mathbf {A} _{2,1}+\mathbf {A} _{2,2})\mathbf {B} _{1,1}

\mathbf {M} _{3}:=\mathbf {A} _{1,1}(\mathbf {B} _{1,2}-\mathbf {B} _{2,2})

\mathbf {M} _{4}:=\mathbf {A} _{2,2}(\mathbf {B} _{2,1}-\mathbf {B} _{1,1})

\mathbf {M} _{5}:=(\mathbf {A} _{1,1}+\mathbf {A} _{1,2})\mathbf {B} _{2,2}

\mathbf {M} _{6}:=(\mathbf {A} _{2,1}-\mathbf {A} _{1,1})(\mathbf {B} _{1,1}+\mathbf {B} _{1,2})

\mathbf {M} _{7}:=(\mathbf {A} _{1,2}-\mathbf {A} _{2,2})(\mathbf {B} _{2,1}+\mathbf {B} _{2,2})

Сада можемо изразити C_i,j преко M_k:

\mathbf {C} _{1,1}=\mathbf {M} _{1}+\mathbf {M} _{4}-\mathbf {M} _{5}+\mathbf {M} _{7}

\mathbf {C} _{1,2}=\mathbf {M} _{3}+\mathbf {M} _{5}

\mathbf {C} _{2,1}=\mathbf {M} _{2}+\mathbf {M} _{4}

\mathbf {C} _{2,2}=\mathbf {M} _{1}-\mathbf {M} _{2}+\mathbf {M} _{3}+\mathbf {M} _{6}

Пролазимо кроз алгоритам n пута (док подматрице не постану бројеви). На крају треба обрисати преостале нуле.

Обично се при имплементирању Штрасеновог алгоритма за довољно мале подматрице користе стандардне методе, које су у том случају ефикасније. Прелазна тачка на којој Штрасенов алгоритам постаје ефикаснији зависи од имплементације и хардвера. Раније се предвиђало да је Штрасенов алгоритам бржи код матрица димензија између 32 и 128 за оптимизоване имплементације.^[1] Међутим у скорије време се испоставило да се прелазна тачка повећава, истраживање спроведено 2010. године показало је да на тренутним архитектурама чак ни само један корак Штрасеновог алгоритма не доноси предности у односу на оптимизована традиционална множења, док ранг матрица не пређе 1000, па чак и тад, када је ранг до неколико хиљада, предност је маргинална (у најбољем случају 10%).^[2]

Асимптотска сложеност

Стандардно множење матрица има приближно $2 N 3$ (за $N = 2 n$ ) аритметичких операција; асимптотска сложеност је $Θ(N 3)$ .

Број аритметичких операција у Штрасеновом алгоритму може да се израчуна на следећи начин: нека је $f (n)$ број операција за матрицу димензије $2 n \times 2 n$ . Затим рекурзивном применом алгоритма, видимо да је $f (n) = 7 f (n -1) + l 4 n$ , за неко константно ''l које зависи од броја сабирања у конкретној имплементацији алгоритма. Дакле f(n) = (7 + o(1))n, т.ј. асимптотска сложеност за множење матрица димензије N = 2n помоћу Штрасеновог алгоритма је:

O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})

.

Умањењем броја аритметичких операција се ипак смањује нумеричка стабилност,^[3] такође алгоритам захтева знатно више меморије у односу на наивни алгоритам. Димензије обе почетне матрице треба проширити до првог следећег степена двојке, што може повећати број елемената до четири пута и резултовати са седам помоћних матрица таквих да свака има четвртину елемената из проширеног дела.

Ранг или билинеарна сложеност

Билинеарна сложеност или ранг билинеарне мапе је битан концепт у асимптотској сложености множења матрица. Ранг билинеарне мапе $\phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C}$ над пољем F се дефинише као (не баш формална нотација):

R(\phi /\mathbf {F} )=\min \left\{r\left|\exists f_{i}\in \mathbf {A} ^{*},g_{i}\in \mathbf {B} ^{*},w_{i}\in \mathbf {C} ,\forall \mathbf {a} \in \mathbf {A} ,\mathbf {b} \in \mathbf {B} ,\phi (\mathbf {a} ,\mathbf {b} )=\sum _{i=1}^{r}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}\right.\right\}

Другим речима, ранг билинеарне мапе је дужина њеног најкраћег билинеарног рачуна.^[4] Постојање Штрасеновог алгоритма показује да ранг множења 2×2 матрица није већи од седам. Да бисмо се уверили, користимо брзи алгоритам (уз стандардни алгоритам) као такав билинеарни рачун. У случају матрица, дуални простори A* и B* се састоје од мапа у пољу F индукованих скаларним векторским производом, (т.ј. у овом случају збиром свих елемената Хадамардовог производа.)

	Стандардни алгоритам			Штрасенов алгоритам
и	ф_и(а)	г_и(б)	w_и	ф_и(а)	г_и(б)	w_и
1	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}$	${\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}1&0\\0&1\end{bmatrix}}$
2	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}$	${\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\1&-1\end{bmatrix}}$
3	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&1\\0&1\end{bmatrix}}$
4	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}1&0\\1&0\end{bmatrix}}$
5	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}$	${\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}-1&1\\0&0\end{bmatrix}}$
6	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}$	${\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}$
7	${\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}$	${\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}1&0\\0&0\end{bmatrix}}$
8	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b}$	${\begin{bmatrix}0&0\\0&1\end{bmatrix}}$
	$\mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}$			$\mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}$

Може се показати да је укупан број основних множења L потребних за множење матрица асимптотски строго везан за ранг R, т.ј. $L=\Theta (R)$ , или прецизније, пошто су константе познате, ${\frac {1}{2}}R\leq L\leq R$ . Једно од корисних својстава ранга је субмултипликативност за тензорске производе, што нам омогућава да покажемо да множење 2ⁿ×2ⁿ×2ⁿ матрица може бити постигнуто са не више од 7^н основних множења за свако n.

Савети за имплементацију

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

Ради добре имплементације треба приметити:

Није потребно, а ни пожељно користити Штрасенов алгоритам све до скаларних вредности. У односу на конвенционално множење матрица, овај алгоритам додаје још $O(n^{2})$ сабирања и одузимања. Дакле, испод одређене величине, боље је користити конвенционално множење. На пример, ако су почетне матрице димензија 1600x1600, нема потребе допуњавати их до 2048x2048, него је боље поделити их на подматрице 25x25 и користити стандардно множење.
Штрасенов алгоритам такође може да се примени на матрице било којих димензија. Ако је димензија парна онда се матрица дели на начин који је предходно описан, а ако је непарна онда се матрица допуњује нула редом и колоном. Овакво допуњавање се може извршити успут и лењо, а додатни редови и колоне се бришу кад се формира резултат. На пример, рецимо да су матрице димензија 199x199. Оне се могу поделити на два дела: горе-лево, димензија 100x100 и доле-десно, 99x99. Када је потребно 99 се може допунити до 100. Приметимо да се, на пример, производ $M_{2}$ користи само у доњем делу излаза. С обзиром да леви чинилац $(A_{2,1}+A_{2,2})$ има само 99 редова, нема потребе додавати 100. ред у суму. Једино што је потребно додавити је колона у $A_{2,2}$ да би могло да се множи са $A_{2,1}$ .
Осим тога, нема потребе да матрице буду квадратне. Неквадратне матрице се могу поделити користећи исте методе као квадратне, правећи мање неквадратне матрице. Ако је разлика броја редова и колона матрица веома велика, пожељно је направити да матрице буду "квадратније". То се постиже једноставним методама:
- Производ [2N x N] * [N x 10N] се може изразити преко 20 засебних [N x N] * [N x N] операција, сортираних тако да формирају резултат;
- Производ [N x 10N] * [10N x N] се може одредити са 100 [N x N] * [N x N] операција, које се сабирају да би се добио резултат.

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

Референце

^ Скиена, Стевен С. (1998), „§8.2.3 Матриx мултиплицатион”, Тхе Алгоритхм Десигн Мануал, Берлин, Неw Yорк: Спрингер-Верлаг, ИСБН 978-0-387-94860-7
^ D'Алберто, Паоло; Ницолау, Алеxандру (2005). Усинг Рецурсион то Боост АТЛАС'с Перформанце (ПДФ). Сиxтх Инт'л Сyмп. он Хигх Перформанце Цомпутинг.
^ Wебб, Миллер (1975). „Цомпутатионал цомплеxитy анд нумерицал стабилитy”. СИАМ Ј. Цомпут: 97—107.
^ Бургиссер, Цлаусен, анд Схокроллахи. Алгебраиц Цомплеxитy Тхеорy. Спрингер-Верлаг 1997.

Литература

Страссен, Волкер, Гауссиан Елиминатион ис нот Оптимал, Нумер. Матх. 13, п. 354-356, 1969
Тхомас Х. Цормен, Цхарлес Е. Леисерсон, Роналд L. Ривест, анд Цлиффорд Стеин. Интродуцтион то Алгоритхмс, Сецонд Едитион. МИТ Пресс анд МцГраw-Хилл. 2001. ISBN 978-0-262-03293-3.. Цхаптер 28: Сецтион 28.2: Страссен'с алгоритхм фор матриx мултиплицатион, пп. 735–741.

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

Wеисстеин, Ериц W. „Страссен'с Формулас”. МатхWорлд. (такође садржи формуле за брзу инверзију матрица)
Тyлер Ј. Еарнест, Страссен'с Алгоритхм он тхе Целл Броадбанд Енгине
Симпле Страссен'с алгоритхмс имплементатион ин C

[1] Скиена, Стевен С. (1998), „§8.2.3 Матриx мултиплицатион”, Тхе Алгоритхм Десигн Мануал, Берлин, Неw Yорк: Спрингер-Верлаг, ИСБН 978-0-387-94860-7

[dalberto-2] D'Алберто, Паоло; Ницолау, Алеxандру (2005). Усинг Рецурсион то Боост АТЛАС'с Перформанце (ПДФ). Сиxтх Инт'л Сyмп. он Хигх Перформанце Цомпутинг.

[3] Wебб, Миллер (1975). „Цомпутатионал цомплеxитy анд нумерицал стабилитy”. СИАМ Ј. Цомпут: 97—107.

[4] Бургиссер, Цлаусен, анд Схокроллахи. Алгебраиц Цомплеxитy Тхеорy. Спрингер-Верлаг 1997.

[1]

[2]

[3]

[4]