101.650 VO (2std Vorlesung, Sommersemester 2017)
AKNUM: Matrixkompression und H-Matrizen
TISS-Homepage

Ort und Termin

Ziel der LVA

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.

Inhalt der LVA

Elementare Operationen mit N x 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.

Downloads

14.02.2018Skript - komplett (korrigiert)[pdf]
26.06.2017Skript - Kapitel 5: H2-Matrizen[pdf]
12.06.2017Skript - Kapitel 4 (überarbeitet!): H-Arithmetik[pdf]
27.04.2017Skript - Kapitel 3 (gesamt!): Approximation mit H-Matrizen[pdf]
20.03.2017Skript - Kapitel 2: Algebraische Struktur (überarbeitet)[pdf]
21.02.2017Skript - Kapitel 1: Einleitung[pdf]

Termine

#DatumTopicRaum
107.03.2017EinführungSem.R. DA grün 04
214.03.2017Algebraische Struktur hierarchischer MatrizenSem.R. DA grün 04
321.03.2017Konstruktion zul. Partitionen, SingulärwertzerlegungSem.R. DA grün 04
428.03.2017Bestapproximation, InterpolationSem.R. DA grün 04
504.04.2017Asymptotisch glatte Kerne, verbesserter InterpolationsfehlerFH HS 8
625.04.2017Tensorielle Interpolation, H-Matrizen mit InterpolationSem.R. DC rot 07
702.05.2017Adaptive KreuzapproximationSem.R. DC rot 07
809.05.2017Hybride Kreuzapproximation, Rang-r-SVDSem.R. DC rot 07
916.05.2017H-Addition und H-MuliplikationSem.R. DC rot 07
1023.05.2017Vorgeschriebene Zielpartition, H-Inversion, H-LUSem.R. DC rot 07
30.05.2017Dienstreise: Keine Vorlesungentfällt
06.06.2017Pfingsten: Keine Vorlesungentfällt
1113.06.2017RekompressionSem.R. DC rot 07
1220.06.2017H^2-MatrizenSem.R. DC rot 07
1327.06.2017H^2-Matrizen, SchlussworteSem.R. DC rot 07

Leistungsnachweis

Mündliche Prüfung, Terminvereinbarung per E-Mail.

Vorkenntnisse

Für die Vorlesung sind lediglich Grundkenntnisse in numerischer Mathematik nötig.