KIT | KIT-Bibliothek | Impressum | Datenschutz

Exascale Ready Work-Optimal Matrix Inversion

Steffen, Raoul

Abstract:
In dieser Diplomarbeit entwickle ich einen neuen Algorithmus OPT zur Inversion von Matrizen. Ich beweise Eigenschaften zur parallelen Laufzeit und zum Arbeitsaufwand von OPT. OPT ist kombiniert aus Strassens Algorithmus zur Inversion von Matrizen und aus Newton Approximation und basiert auf einer Subroutine zur Matrixmultiplikation.
OPT ist ein arbeitsoptimaler Algorithmus, d.h. er benötigt höchstens einen konstanten Faktor mehr Arbeit als jeder andere (arbeitsoptimale) Algorithmus. Außerdem benötigt OPT nur plylogarithmische Zeit auf höchstens O(n3) Prozessoren, wobei die Prozessorzahl von der Multiplikationsroutine bestimmt wird. ... mehr

Abstract (englisch):
In this thesis I present a new algorithm OPT for matrix inversion that builds on a matrix multiplication subroutine. It is combined of Strassen's matrix inversion algorithm and Newton approximation. OPT overcomes the linear lower bound in parallel runtime of Strassen's inversion algorithm and traditional Gaussian elimination without the log-factor more work of
Newton approximation. In particular I prove, that given a work-optimal multiplication subroutine that runs in polylog time, OPT not only runs in polylog time, too, but furthermore only needs a constant factor more work than any work-optimal inversion algorithm.
Additionally, I present a new stability result for Strassen's matrix inversion algorithm combined with Newton approximation.
As part of this thesis, I implemented OPT, Strassen's inversion algorithm, and Newton approximation in a exible test program along with a matrix container class optimized for this purpose. ... mehr

Open Access Logo


Volltext §
DOI: 10.5445/IR/1000048583
Coverbild
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Hochschulschrift
Jahr 2012
Sprache Englisch
Identifikator urn:nbn:de:swb:90-485839
KITopen-ID: 1000048583
Verlag KIT, Karlsruhe
Umfang 51 S.
Abschlussart Abschlussarbeit - Diplom
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page