von Wolfgang Hackbusch

Teil I

Aktueller Forschungsschwerpunkt Wissenschaftliches Rechnen

Die folgenden Ausführungen betreffen das Wissenschaftliche Rechnen speziell im Bereich der numerischen Behandlung von partiellen Differentialgleichungen, wie sie vielfältig in der Physik und Technik auftreten.

Die Inhalte des Wissenschaftlichen Rechnens werden durch den Rechner, seine Fähigkeiten und Entwicklungen geprägt. Dies soll im folgenden am Beispiel des Begriffes ``lineare Komplexität'' erläutert werden. Anschließend wird ein spezielles neues Projekt vorgestellt: Die hierarchischen Matrizen erlauben Aufgaben mit fast linearem Aufwand zu behandeln, die früher außerhalb der Reichweite schienen.

Großskalige Aufgaben

Die klassischen Feldgleichungen der Physik beschreiben die Zustände als Funktionen der drei Raum- und eventuell der Zeitdimension, wobei die Funktionen über Gleichungen bestimmt werden, in denen die Ableitungen der gesuchten Funktionen auftreten. Da nur in Ausnahmefällen Lösungen geschlossen bekannt sind, ist man auf die numerische Rechnung angewiesen, die jedoch nur Annäherungen (Approximationen) liefern kann. Die Überführung der unendlichdimensionalen Differentialgleichung in ein endliches Problem wird als Diskretisierung bezeichnet. Da die Approximationsgüte weiter gesteigert und immer komplexere Aufgaben in Angriff genommen werden sollen, kommt es dazu, daß die anfallenden Rechnungen in ihrem Umfang nur durch die Kapazität des Rechners beschränkt werden.

In den 60er Jahren begann man, von räumlich eindimensionalen Modellen auf solche in zwei Raumdimensionen überzugehen. In den 80er Jahren wurde begonnen, die vollen dreidimensionalen Probleme in Angriff zu nehmen. Wie schnell die Rechnerkapazität überschritten wird, erkennt man sofort, wenn man a) das Intervall [0,1] durch ein Gitter mit 1000 Punkten, b) das Einheitsquadrat durch ein quadratisches Gitter mit 1000 1000 Punkten und c) den Einheitswürfel durch ein kubisches Gitter mit 1000 1000 1000 Punkten ersetzt und pro Punkt die gesuchte Funktion bestimmen möchte. Im einfachsten Fall erhält man ein lineares Gleichungssystem, wobei die Zahl der Gleichungen und Unbekannten mit der Zahl der sogenannten Diskretisierungspunkte übereinstimmt.

Ein wichtiges Ziel ist es, eine möglichst gute Annäherung mit einer möglichst niedrigen Zahl von Unbekannten zu erreichen. Je größer (und damit unüberschaubarer) die Datenmenge wird, um so wichtiger ist es, die Gestaltung der Diskretisierung vom Anwender auf das Computerprogramm zu übertragen. Damit das Verfahren seine eigene Zuverläßlichkeit garantieren kann, werden strenge mathematische Aussagen benötigt.

Der Rechner ist kein zeitunabhängiges Hilfsmittel. Seit Einführung der ersten Rechner stellt man fest, daß sich die Größe des Rechenspeichers ebenso wie die Rechengeschwindigkeit in einem bestimmten Zeitraum jeweils verdoppelt. Im weiteren ist es wesentlich, daß das Wachstum von Speicher und Geschwindigkeit proportional ist.

Lineare Komplexität

Gegeben sei die Aufgabe, aus n Eingabedaten ebenso viele Ausgabedaten zu erzeugen. Da für jedes Ausgabedatum im allgemeinen mindestens eine Rechenoperation benötigt, ist der benötigte Rechenaufwand R(n) mindestens proportional zu n: . In diesem optimalen Fall sprichtman von linearer Komplexität. Im Falle eines Gleichungssystems der Dimension n benötigt die klassische Gauß-Elimination dagegen einen kubischen Rechenaufwand .

Eine einfache Überlegung zeigt die folgende paradoxe Situation. Ein Verfahren der Komplexität angewandt mit n an der Grenze der Rechnerkapazität benötigt eine Rechenzeit, die um ansteigt, wenn nach einer Rechner-Reinvestition ein neuer, um den Faktor c>1 größerer und schnellerer Rechner eingesetzt wird (Da die Datenmenge auf cn ansteigt, sind Operationen durchzuführen, während die Rechenzeitbeschleunigung einen Faktor liefert). Damit kommen auf längere Dauer nur Verfahren linearer Komplexität in Frage, da dann Weil andererseits lineare Komplexität die bestmögliche ist, bedeutet dies eine große Herausforderung an den Algorithmenentwurf.

Im Falle der Lösung linearer Gleichungen läßt sich lineare Komplexität zwar nicht generell erreichen, aber wenn die Gleichungen durch die Diskretisierung einer partiellen Differentialgleichung gewonnen wurden, haben sie weitere mathematische Eigenschaften, die durch geeignete Algorithmen ausgenutzt werden können. Die vom Autor mit eingeführten Mehrgitterverfahren ermöglichten es erstmals, große Klassen von diskretisierten partiellen Differentialgleichungen mit linearer Komplexität zu lösen.

weiter mit dem nächsten Teil

• Teil 1
  • Aktueller Forschungsschwerpunkt Wissenschaftliches Rechnen
  • Großskalige Aufgaben
  • Lineare Komplexität
• Teil 2
  • Vollbesetzte Gleichungssysteme
  • Approximation vollbesetzter Matrizen
• Teil 3
• Hierarchische Matrizen
• Ausblick

Kontakt

Prof. Dr. Wolfgang Hackbusch
Max-Planck Institut für Mathematik in den Naturwissenschaften
Inselstrasse 22
04103 Leipzig
Email