Scientific Computing

Matrix-Galerkin-Verfahren

Beteiligte: Steffen Börm, Dirk Boysen.

In vielen Bereichen der numerischen Mathematik treten Matrixgleichungen auf, beispielsweise sind in der Steuerungstheorie die Lyapunov-Gleichung AX+XA=B, die Sylvester-Gleichung AX+XB=C und die Riccati-Gleichung AX+XA+XBX=C von Interesse, bei der Behandlung stochastischer Differentialgleichungen treten Gleichungen der Form AXA=B auf, während für das Lösen linearer Gleichungssysteme die Gleichungen AX=I und XA=I eine Rolle spielen. Ohne weitere Annahmen an die Lösung X erfordert das Lösen dieser Gleichungen mindestens einen Aufwand, der quadratisch mit der Problemdimension wächst und damit schnell den Rahmen dessen sprengt, was ein typischer Computer leisten kann.

In manchen Anwendungen weiß man allerdings, dass die Lösung X eine Struktur aufweist, die es uns ermöglicht, sie durch eine H²-Matrix zu approximieren, deren Speicherbedarf lediglich linear mit der Dimension wächst, so dass sich auch die Lösungen relativ großer Probleme effizient darstellen lassen sollten. Es stellt sich allerdings die Frage, wie diese Lösungen praktisch berechnet werden können.

Unsere Antwort entsteht aus dem Galerkin-Ansatz: Wenn wir Gleichung in einem geeigneten Skalarprodukt mit Testmatrizen multiplizieren, entsteht ein großes lineares Gleichungssystem, in dem die meisten Koeffizienten gleich null sind. Dieses System lässt sich mit iterativen Lösungsverfahren behandeln, um beliebig genaue Näherungen der Matrix X zu erhalten. Dabei treten zwei Herausforderungen auf: Erstens muss das lineare Gleichungssystem effizient aufgestellt werden, zweitens muss es anschließend auch effizient gelöst werden. Für die erste Aufgabe entwickeln wir neuartige Algorithmen, die die Struktur einer H²-Matrix geschickt ausnutzen, für die zweite Aufgabe kommt ein wesentlich verallgemeinertes Mehrgitterverfahren zum Einsatz.