Das Ziel dieser Lehrveranstaltung ist eine Einführung in das Matrixkompressionsformat der hierarchischen Matrizen (H-Matrizen) zu geben, mathematisch zu analysieren für welche Problemklassen eine sinnvolle Anwendbarkeit gegeben ist, sowie essentielle Algorithmen vorzustellen und deren Aufwand zu analysieren.
Weitere Kompressionstechniken wie H^2-Matrizen werden ebenfalls vorgestellt.
Die Lehrveranstaltung gehört zum AKNUM Wahlfachkatalog.
Elementare Operationen mit N × N -Matrizen, wie beispielsweise Addition oder Matrix-Vektor-Multiplikation (MVM) benötigen üblicherweise mindestens O(N^2) arithmetische Operationen, was bei großskaligen Problemen einen nicht praktikablen Rechenaufwand darstellt.
Um die Speicherung und MVM für eine gewisse (wichtige) Klasse von vollbesetzten Matrizen (z.B. bei Diskretisierung von Integraloperatoren) in linearer Komplexität O(N) (approximativ) zu gewährleisten, entstand 1987 die Fast Multipole Methode (FMM), welche in weiterer Folge zu einem der Top 10 Algorithmen des 20. Jahrhunderts gewählt wurde.
Eine algebraische Verallgemeinerung der FMM entstand 1999 mit dem Matrixkompressionsformat der hierarchischen Matrizen (H-Matrizen). Im Vergleich zu anderen Kompressionsverfahren (wie auch der FMM) erlauben H-Matrizen nicht nur Speicherung und MVM in (logarithmisch) linearer Komplexität, sondern auch weitere (approximative) arithmetische Operationen wie Addition, Multiplikation und Inversion mit Aufwand O(N log N).
In dieser Lehrveranstaltung wird das Format der hierarchischen Matrizen vorgestellt und mathematisch und algorithmisch analysiert. Schlussendlich werden weitere Kompressionstechniken wie H^2-Matrizen (lineare Komplexität O(N)) vorgestellt.
