Strassen algoritmus

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. november 22-én felülvizsgált verziótól ; az ellenőrzések 20 szerkesztést igényelnek .

Strassen algoritmusát gyors mátrixszorzásra tervezték . Volker Strassen fejlesztette ki 1969-ben, és a Karatsuba mátrixszorzási módszerének általánosítása.

A hagyományos , időben futó mátrixszorzó algoritmustól eltérően (a képlet szerint ) , a Strassen-algoritmus időben szorozza a mátrixokat , ami nagy sűrűségű mátrixokon erősít. ${\displaystyle c_{ij}=\sum a_{ik}b_{kj))$ $\Theta (n^{{\log _{2}8)))=\Theta (n^{3})$ $\Theta (n^{{\log _{2}7)))=O(n^{{2,81)))$

Annak ellenére, hogy a Strassen-féle algoritmus aszimptotikusan nem a leggyorsabb a meglévő gyors mátrixszorzó algoritmusok közül, könnyebben programozható és hatékonyabb viszonylag kis mátrixok szorzásakor, így a gyakorlatban ez a leggyakrabban használt.

Az algoritmus leírása

Ha ugyanazokat a nulla sorokat és oszlopokat adjuk hozzá a mátrixokhoz , akkor a szorzatuk egyenlő lesz az azonos hozzáadott sorokkal és oszlopokkal rendelkező mátrixszal. Ezért csak a méretű mátrixok jöhetnek számításba , más eseteket pedig nullák hozzáadásával lehet erre redukálni, ami csak megduplázódhat. $A$ $B$ $AB$ ${\displaystyle n=2^{k},\ k\in {\mathbb {N} ))$ $n$

Legyenek méretű mátrixok . A -mátrixokból származó méretű blokkmátrixokként ábrázolhatók: $A,B$ ${\displaystyle 2^{k}\times 2^{k))$ $(2\x 2)$ $(2^{k-1}\szer 2^{k-1})$

A={\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix)),\quad B={\begin{pmatrix}B_{11} &B_{12}\\B_{21}&B_{22}\end{pmatrix}}

A blokkszorzás elve alapján egy mátrixot a szorzatukban fejeznek ki $AB$

AB={\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}}\ ,

ahol a jobb oldalon nyolc méretű mátrix szorzata található . Mivel a mátrixok egy gyűrűt alkotnak , így a jobb oldal kiszámítására bármely olyan -mátrixok szorzására szolgáló algoritmus alkalmas , amely csak összeadást, kivonást és szorzást használ. Strassen a következő algoritmust javasolta hét szorzással: $2^{k-1}\times 2^{k-1}$ $(2\x 2)$

{\begin{aligned}D&=(A_{11}+A_{22})(B_{11}+B_{22});\\D_{1}&=(A_{12}-A_{ 22})(B_{21}+B_{22});\\D_{2}&=(A_{21}-A_{11})(B_{11}+B_{12});\\H_{ 1}&=(A_{11}+A_{12})B_{22};\\H_{2}&=(A_{21}+A_{22})B_{11};\\V_{1} &=A_{22}(B_{21}-B_{11});\\V_{2}&=A_{11}(B_{12}-B_{22});\\\end{igazított}}

{\begin{aligned}AB&={\begin{pmatrix}D&0\\0&D\end{pmatrix}}+{\begin{pmatrix}D_{1}&0\\0&D_{2}\end{pmatrix} }+{\begin{pmatrix}-H_{1}&H_{1}\\H_{2}&-H_{2}\end{pmatrix}}+{\begin{pmatrix}V_{1}&V_{2} \\V_{1}&V_{2}\end{pmatrix}}\\&={\begin{pmatrix}D+D_{1}+V_{1}-H_{1}&V_{2}+H_{1 }\\V_{1}+H_{2}&D+D_{2}+V_{2}-H_{2}\end{pmatrix}}\ .\end{igazított}}

Minden szorzás elvégezhető rekurzív módon ugyanazzal az eljárással, és az összeadást triviálisan, elemek hozzáadásával. Ezután a rekurzív reláción keresztül megbecsüljük az algoritmus futási idejét : $(2^{k-1})^{2}$ $T(n)$

T(n)=7T(n/2)+O(n^{2})=O(n^{\log _{2}7})\ .

Megvalósítási példa

Az alábbiakban egy példa az algoritmus Pythonban való megvalósítására, amely a NumPy könyvtárat használja az almátrixok gyors felvételéhez. A fő funkció a strassen_mul. Feltételezzük, hogy minden mátrix négyzet alakú, típussal ábrázolva, numpy.arrayméretük pedig 2 hatványa.

Kis mátrixméretek esetén a közvetlen szorzás gyorsabb, mint a Strassen-algoritmus az utóbbiban található nagyszámú összeadás miatt. Az ilyen méretek határa az elemek összeadási és szorzási idejének arányától függ, ezért a hardverkörnyezettől függően változhat. A kódban a konstans felelős a célért TRIVIAL_MULTIPLICATION_BOUND.

itertoolsból import termék import numpy as np _ def split_to_2x2_blocks ( mátrix ): visszatérési lista ( térkép ( lambda sor : np . hsplit ( sor , 2 ), np . vsplit ( mátrix , 2 ) )) def strassen_mul_2x2 ( lb , rb ): d = strassen_mul ( lb [ 0 ][ 0 ] + lb [ 1 ][ 1 ], rb [ 0 ][ 0 ] + rb [ 1 ][ 1 ]) d_1 = strassen_mul ( lb [ 0 ][ 1 ] - lb [ 1 ][ 1 ], rb [ 1 ][ 0 ] + rb [ 1 ][ 1 ]) d_2 = strassen_mul ( lb [ 1 ][ 0 ] - lb [ 0 ][ 0 ], rb [ 0 ][ 0 ] + rb [ 0 ][ 1 ]) bal = strassen_mul ( lb [ 1 ][ 1 ], rb [ 1 ][ 0 ] - rb [ 0 ][ 0 ]) jobb = strassen_mul ( lb [ 0 ][ 0 ], rb [ 0 ][ 1 ] - rb [ 1 ][ 1 ]) felső = strassen_mul ( lb [ 0 ][ 0 ] + lb [ 0 ][ 1 ], rb [ 1 ][ 1 ]) alsó = strassen_mul ( lb [ 1 ][ 0 ] + lb [ 1 ] [ 1 ], rb [ 0 ][ 0 ]) return [[ d + d_1 + bal - fent , jobb + felül ], [ bal + lent , d + d_2 + jobb - lent ]] def trivial_mul ( bal , jobb ): magasság , mid_size = bal . alak közepes méretű , jobb = jobb . formák eredmény = np . nullák (( magasság , szélesség )) a sorhoz , oszlophoz , a termék közepéhez ( * térkép ( tartomány , [ magasság , szélesség , mid_size ])): eredmény [ sor ][ oszlop ] += bal [ sor ][ mid ] * jobb [ közép ][ oszlop ] vissza az eredményt TRIVIAL_MULTIPLICATION_BOUND = 8 def strassen_mul ( left , right ): assert ( left . shape == right . shape ) assert ( left . shape [ 0 ] == left . shape [ 1 ]) ha marad . shape [ 0 ] <= TRIVIAL_MULTIPLICATION_BOUND : return trivial_mul ( balra , jobbra ) assert ( balra . alak [ 0 ] % 2 == 0 ) return np . blokk ( strassen_mul_2x2 ( * térkép ( split_to_2x2_blocks , [ balra , jobbra ]))) )

Továbbfejlesztés

Strassen volt az első, aki megmutatta a mátrixok szabványosnál hatékonyabb szorzásának lehetőségét. Munkájának 1969-es publikálása után megkezdődött a gyorsabb algoritmusok aktív keresése. Napjaink aszimptotikusan leggyorsabb algoritmusa az 1987-ben javasolt és 2011-ben az [1] szintre továbbfejlesztett Coppersmith-Winograd algoritmus , amely lehetővé teszi a mátrixok szorzását műveletekben [ 1] . Ennek az algoritmusnak nincs gyakorlati jelentősége, mivel a csillagászatilag nagy konstans az aritmetikai komplexitás becslésében. A mátrixszorzás aszimptotikusan korlátozó sebességének kérdése nem megoldott. Létezik Strassen sejtése, hogy kellően nagy esetén létezik egy algoritmus két méretű mátrix megszorzására olyan műveletekben, ahol egy előre megadott pozitív szám tetszőlegesen kicsi. Ez a sejtés pusztán elméleti érdeklődésre tarthat számot, mivel a mátrixok mérete, amelyekhez valóban kicsi, láthatóan nagyon nagy. ${{\rm {O}}}(n^{{2,376}})$ ${{\rm {O}}}(n^{{2,3727}})$ $n$ $n\szer n$ ${{\rm {O}}}(n^{{2+\varepszilon }})$ $\varepsilon$ $\varepsilon$

A nagy mátrixok szorzására szolgáló leggyorsabb és legstabilabb gyakorlati algoritmus megalkotásának kérdése szintén megoldatlan marad.

Winograd-Strassen algoritmus

A Strassen-algoritmusnak van egy olyan módosítása, amely 7 szorzást és 15 összeadást igényel (a szokásos Strassen-algoritmus 18 helyett).

A mátrixok blokk-almátrixokra vannak felosztva, ahogy fentebb látható. ${\megjelenítési stílus A,\,B,\,C}$

A köztes elemek kiszámítása megtörténik $S_{1},\,\ldots ,\,S_{8},\,P_{1},\,\ldots ,\,P_{7},\,T_{1},\,T_{ 2}$

{\begin{aligned}S_{1}&=(A_{21}+A_{22});\\S_{2}&=(S_{1}-A_{11});\\S_ {3}&=(A_{11}-A_{21});\\S_{4}&=(A_{12}-S_{2});\\S_{5}&=(B_{12} -B_{11});\\S_{6}&=(B_{22}-S_{5});\\S_{7}&=(B_{22}-B_{12});\\S_ {8}&=(S_{6}-B_{21});\\P_{1}&=S_{2}S_{6};\\P_{2}&=A_{11}B_{11} ;\\P_{3}&=A_{12}B_{21};\\P_{4}&=S_{3}S_{7};\\P_{5}&=S_{1}S_{5 };\\P_{6}&=S_{4}B_{22};\\P_{7}&=A_{22}S_{8};\\T_{1}&=P_{1}+P_ {2};\\T_{2}&=T_{1}+P_{4}.\end{igazított}}

A mátrixelemek kiszámítása a következőképpen történik: $C$

{\begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{pmatrix}}={\begin{pmatrix}P_{2}+P_{3}&T_ {1}+P_{5}+P_{6}\\T_{2}-P_{7}&T_{2}+P_{5}\end{pmatrix}}.

A probléma jelenlegi állása

A Strassen-algoritmus egy bilineáris algoritmus, együtthatói a Brent -egyenletek köbrendszerének gyökerei . [2] A <2x2x2> egzakt algoritmusok osztályánál ez egy minimális probléma, melynek megoldása lehetővé teszi a szorzások számának csökkentését a mátrixelemek gyűrűjében. [3] [4] Az új algoritmusok megtalálásának problémája, hogy a Brent-rendszer nemlineáris, az ismeretlenek és egyenletek száma (ezek a számok nem esnek egybe) gyorsan nő a mátrixok méretével, és csak a nagy nullák száma kötelező.

2013-ban ezeknek a problémáknak a részleges leküzdése után sikerült megtalálni az első gyakorlati bilineáris mátrixszorzási algoritmust, amely aszimptotikusan gyorsabb, mint a Strassen-algoritmus. [5] Szmirnov algoritmusa <3x3x6; 40> megszoroz egy 3x3-as mátrixot egy 3x6-os mátrixszal, 54 helyett 40 szorzást használva. Aszimptotikus komplexitása . (Az algoritmus tenzoros szorzása önmagával az argumentumok ciklikus eltolásával, az <54x54x54; 64000> négyzetmátrixok ugyanolyan bonyolultságú algoritmusához vezet). A szorzás valódi felgyorsításához jelentős optimalizálás szükséges - sok párhuzamos számítás eltávolítása lineáris formában. $O(n^{\log _{54}64000})=O(n^{2,78})$

Ma (2022) ez aszimptotikusan a leggyorsabb gyakorlati bilineáris algoritmus mátrixelemek tetszőleges mezőjére .

2022. október 5-én a DeepMind az AlphaZero neurális hálózati algoritmust használva számos új algoritmust talált különböző dimenziójú mátrixok szorzására. Azonban ezek sebessége egy tetszőleges mező esetén messze van az ismert legjobb algoritmusok sebességétől. Tehát a 4X4-es mátrixokhoz a Strassen-algoritmus 49 szorzást igényel, az AlphaTensor pedig talált egy olyan algoritmust, amely 47 szorzást igényel, de ez csak a mezőben működik . [6] [7] $\mathbb{Z } _{2}$

Jegyzetek

↑ 1 2 A matematikusok legyőzték a Coppersmith-Winograd akadályt . lenta.ru (2011. december 12.). Hozzáférés dátuma: 2011. december 12. Az eredetiből archiválva : 2012. február 5. (határozatlan)
↑ RPBrent. Algoritmusok mátrixszorzásokhoz// Computer Science Dept. Jelentés CS 157, Stanford University, 1970.
↑ A mátrixszorzás összetettsége. Áttekintés//Cybernetic. Gyűjtemény. 1988. szám. 25. S. 139-236.
↑ Landsberg JM Geometria és a mátrixszorzás összetettsége // Bull. amer. Math. szoc. 2008. V.45. P. 247-284.
↑ A. V. Smirnov, „A bilineáris komplexitásról és a mátrixszorzás gyakorlati algoritmusairól”, Zh. Vychisl. matematika. és mat. Fiz., 53:12 (2013), 1970–1984; Comput. Math. Math. Phys., 53:12 (2013), 1781–1795
↑ Új algoritmusok felfedezése az AlphaTensor segítségével . www.deepmind.com . Letöltve: 2022. október 6.
↑ Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes. Gyorsabb mátrixszorzó algoritmusok felfedezése megerősítéses tanulással // Természet . – 2022-10. — Vol. 610 , iss. 7930 . — P. 47–53 . — ISSN 1476-4687 . - doi : 10.1038/s41586-022-05172-4 .

Irodalom

Strassen V. A Gauss-elimináció nem optimális // Szám . Math / F. Brezzi - Springer Science + Business Media , 1969. - Vol. 13, Iss. 4. - P. 354-356. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF02165411
Levitin A. V. Fejezet 4. Dekompozíciós módszer: Nagy egészek szorzása és a Strassen-mátrixszorzó algoritmus // Algorithms. Bevezetés a fejlesztésbe és elemzésbe - M . : Williams , 2006. - S. 189-195. — 576 p. — ISBN 978-5-8459-0987-9
Kormen, Thomas H., Leiserson, Charles I., Rivest, Ronald L., Stein, Clifford. 28. fejezet. Munka mátrixokkal // Algoritmusok: Konstrukció és elemzés = Bevezetés az algoritmusokba. — 2. kiadás. - M . : "Williams" , 2005. - S. 833 - 839. - ISBN 5-8459-0857-4 .