t_0 t_{-1} .. t_{-n+2} t_{-n+1}
t_1 t_0 t_{-1} t_{-n+2}
T_n = . t_1 . . .
. . . . .
t_{n-2} . t_0 t_{-1}
t_{n-1} t_{n-2} .. t_1 t_0 .
Zur Lösung linearer Gleichungssysteme T_nx=b existieren verschiedene
Arten von schnellen und superschnellen Algorithmen.
Zum einen gibt es die klassischen O(n^2)-Algorithmen (Levinson, Schur).
Diese Verfahren berechnen z.B. rekursiv die Lösungen der
Gleichungssyteme
T_0x_0=b_0, T_1x_1=b_1,..., mit den wachsenden Hauptuntermatrizen
T_0, T_1, bis T_n. Zu diesen klassischen Verfahren gibt es
inzwischen numerisch stabile Erweiterungen für indefinite Matrizen,
z.B. die sogenannten Look-ahead-methoden.
Des weiteren gibt es im positiv definiten Fall die auf divide-and-conquer basierenden superschnellen Algorithmen in O(n log(n)^2) Operationen. Hier wird z.B. die Ausgangsmatrix in Blöcke der halben Größe zerlegt, und das Ausgangsproblem auf diese kleineren Blöcke reduziert.
Zum anderen haben sich in vielen Fällen auch iterative Verfahren als sehr geeignet erwiesen. Für einige Klassen von Toeplitzmatrizen reduziert sich der Aufwand dabei auf O(n log(n)) Operationen. Als Präkonditionierer werden hier z.B. geeignete Bandmatrizen benutzt oder Matrizen, die mit der Fourier- oder Sinustransformation verknüpft sind.
Aufgabe einer Diplomarbeit soll es nun sein, einen Algorithmus aus
einer der oben beschriebenen Klassen
genauer zu analysieren und zu implementieren.
e-mail: huckle@informatik.tu-muenchen.de ,Tel.: 089 2105 2020, Zimmer 2218, Arcisstr. 21