A Strassen-algoritmus négyzetes mátrixok szorzását a klasszikus mátrixszorzásnál kevesebb szorzással oldja meg. 1969-ben írta le Volker Strassen német matematikus.
Az algoritmus alapötlete és leírása
Mátrixszorzás illusztrálása. Például: az mátrix első sora szorozva a mátrix második oszlopával, megadja a mátrix elemét.
2×2-es mátrixok klasszikus szorzása a következőképpen valósítható meg. Legyen
a két összeszorzandó mátrix. A szorzás eredménye a
mátrix, ahol
Strassen ötlete a mátrix kiszámítására az, hogy a fenti 8 szorzás helyett 7-et használjon. Ha
akkor egyszerű számítással bizonyítható, hogy
Ebben az esetben az összeadások száma viszont 18-ra nő.
Legyen . Felosztjuk a mátrixokat típusú mátrixokra, és alkalmazzuk Strassen módszerét ezen mátrixok szorzására is.
Ezt a felbontást addig végezzük, ameddig csak lehet, és minden esetben alkalmazzuk a Strassen elképzelését mátrixok szorzására, függetlenül attól, hogy elemei mátrixok vagy számok.
Az algoritmus elemzése
Ha , akkor legyen a szorzások száma, pedig az összeadások száma.
Felírhatjuk a következő rekurzív összefüggéseket
Ennek megoldása
(A itt a kettes alapú logaritmust jelöli.)
A klasszikus mátrixszorzás esetében a szorzások száma , a Strassen-algoritmus esetében, ha , akkor a szorzások száma lecsökkenthető -re. Ez az eredmény elméleti szempontból fontos, mivel a kitevő értékét 3 alá csökkentette.
Hasonló módon számítható ki az összeadások száma
Innen
A klasszikus mátrixszorzás esetében az összeadások száma .
Ma már létezik ennél is gyorsabb algoritmus, az ún. Coppersmith–Winograd-algoritmus, amely kb. szorzást igényel.[1]
Jegyzetek
↑Coppersmith, Don; Winograd, Shmuel: "Matrix multiplication via arithmetic progressions, Journal of Symbolic Computation 9 (3): 1990, p.251. Online hozzáférés
Források
Sara Baase: Computer Algorithms. Introduction to Design and Analysis, Addison-Wesley Publishing Company, 1983.
T. H. Cormen, C. E. Leiserson, R. R. Rivest, C. Stein, Új algoritmusok, Scolar Kiadó, Budapest, 2003.