101.264 VO (2std Vorlesung, Sommersemester 2009)
AKNUM: Hierarchische Matrizen und Fast Multipole Method
TISS-Homepage

Vorlesungstermin

Freitags 08:30 - 10:00 Uhr, Seminarraum 101 C (4. Stock, grün)

Downloads

22.04.2010aktuelle Version (exkl. Kapitel 1)[pdf]
17.06.2009Kapitel 5[pdf]
04.06.2009Kapitel 4[pdf]
25.05.2009Kapitel 3 (leicht überarbeitet -> blau)[pdf]
20.05.2009Kapitel 3 (bis inkl. Abschnitt 3.6)[pdf]
19.05.2009Kapitel 3 (bis inkl. Abschnitt 3.6.1, leicht überarbeitet)[pdf]
19.05.2009Kapitel 2 (leicht überarbeitet -> rot)[pdf]
23.04.2009Kapitel 3 (Abschnitte 3.1-3.4.1)[pdf]
03.04.2009Kapitel 3 (Abschnitt 3.1)[pdf]
17.03.2009Kapitel 2 (Abschnitt 2.1-2.6)[pdf]

Inhalt der LVA

Die Teilnehmer der LVA sollen an ein aktuelles Forschungsgebiet der Numerischen Mathematik herangeführt werden. Die Fast Multipole Methode (FMM) ist einer der wichtigsten Algorithmen im modernen Scientific Computing. Die Vorlesung kann durchaus zur Vorbereitung auf eine Bachelor- oder Diplomarbeit dienen. Bestehende Kooperationen mit TU-internen Anwendern erlauben dabei einen Anwendungs- und Praxisbezug.

Die FMM wurde 1987 von Greengard und Rokhlin (Yale University) entwickelt. Sie erlaubt den Aufbau, die Speicherung und die Matrix-Vektor-Multiplikation (gewisser, in der Praxis wichtiger) vollbesetzter N x N Matrizen mit Aufwand O(N). Naive Realisierung würde hingegen für die Speicherung N^2 Speicherplätze und für die Matrix-Vektor-Multiplikation O(N^2) arithmetische Operationen erfordern. In den SIAM News wurde die Fast Multipole Methode deshalb zu einem der Top 10 Algorithmen der Numerischen Mathematik gewählt.

In 1999 wurde von Hackbusch (Max-Planck-Institut Leipzig) eine Matrix-Version der FMM entwickelt. Unter dem Begriff "Hierarchische Matrix" (H-Matrix) fasste Hackbusch die Eigenschaften von FMM-Matrizen in einer mathematischen Definition. Man kann eine Hierarchische Matrix als geeignetes Speicherformat (oder Datenkompressionsformat) von FMM-Matrizen verstehen. Dadurch wurde es möglich, für FMM-Matrizen effiziente Algorithmen für elementare Matrix-Operationen (Addition, Multiplikation, Inversion, Berechnung der LU-Faktorisierung etc.) zu entwickeln.

Die wichtigsten Algorithmen sollen in der Vorlesung vorgestellt und analysiert werden. Dies umfasst auch jüngste Resultate wie z.B. die Addition und die Multiplikation von H^2-Matrizen mit Aufwand O(N).

Die Vorlesung richtet sich in erster Linie an Mathematiker und (aufgrund der vergleichsweise hübschen Algorithmen) an Informatiker. Aufgrund Ihrer Anwendungsrelevanz sollte Sie aber auch für Studenten der Physik oder Ingenieurswissenschaften interessant sein.

Für das Verständnis sind lediglich Grundkenntnisse in Mathematik sowie Programmierkenntnisse in einer höheren Programmiersprache nötig.

Aufbau der LVA