Robuste AMG-Methoden und deren Parallelisierung

Seit dem Erscheinen der bahnbrechenden Arbeiten von A. Brandt, S. McCormick, J.W. Ruge, K. Stüben und anderen Anfang der achtziger Jahre, haben sich die Algebraischen Mehrgittermethoden (AMG-Methoden) zu einem mächtigen Werkzeug zur Lösung von großdimensionierten Finite-Elemente-, Finite-Differenzen- oder Finite-Volumen-Gleichungen entwickelt. Es gibt wenigsten zwei typische Situationen, in denen AMG-Methoden sehr erfolgreich eingesetzt werden können: Die Diskretisierung stellt keine Vernetzungshierarchie bereit (das ist typisch für kommerzielle Finite-Elemente-Packete) oder das gröbste Gitter in einer geometrischen Mehrgittermethode ist viel zu fein, um es hinreichend effektiv mit einer Standardmethode lösen zu können (das ist typisch für komplexe praktische Anwendungen). In beiden Fällen werden effektive und robuste AMG-Methoden benötigt. Die Entwicklung von universellen AMG-Methoden mit diesen Eigenschaften bleibt ganz bestimmt ein unerfüllbarer Traum. Für bestimmte, praktisch interessante Klassen von Problemen ist es aber sicherlich möglich hocheffektive und bezüglich dieser Klasse robuste AMG-Methoden zu entwickeln. Eine Aufgabenklasse, für die bereits die klassischen AMG-Verfahren sehr effektiv arbeiten, ist mit den sogenannten M-Matrizen verbunden. Im vorgeschlagenen Projekt wollen wir einen relativ allgemeinen Zugang zur Konstruktion von AMG-Methoden erarbeiten, der es uns erlauben wird, für spezielle, wohldefinierte Klassen von Problemen hocheffektive und robuste AMG-Verfahren zu entwickeln. Dabei haben wir großdimensionierte algebraische Gleichungssysteme im Auge, die bei der Diskretisierung der Maxwell-Gleichungen in der Elektrotechnik, von bestimmten strukturmechanischen Modellen in der Festkörpermechanik etc. entstehen. Diese Klassen von Problemen haben bestimmte Eigenschaften, die dazu führen, daß die standarden AMG-Verfahren versagen. Ein weiteres Ziel des vorgeschlagenen Projekts besteht darin, die Lücke zwischen symmetrischen und positiv definiten (SPD) M-Matrizen und allgemeinen SPD Matrizen in der Klasse der Finite-Element-Steifigkeitsmatrizen mit Blick auf die Anwendbarkeit der standarden AMG-Methoden weiter zu verkleinern. Dazu wollen wir in diesem Projekt die von uns vorgeschlagene Elementvorkonditionierungstechnik weiterentwickeln. Aus rein praktischer Sicht ist die Parallelisierung von AMG- Methoden eine zunehmend wichtige Aufgabe. Die Parallelisierung eröffnet uns die Chance, die Komplexität der zu lösenden Probleme prinzipiell zu vergrößern. Dieses Potential wird nur durch die Anzahl und Leistungsfähigkeit der Prozessoren und die Schnelligkeit des Netzwerkes beschränkt. Die PC-Cluster-Technik wird in den nächsten Jahren hier einen breiten Anwenderkreis die Möglichkeit eröffnen, Parallelrechentechnik zu einen unglaublich günstigen Preis-Leistungs-Verhältnis zu erwerben. Zur Parallelisierung von AMG-Methoden werden wir ein bereits für Gebietsdekompositionsverfahren bewährtes Konzept weiterentwickeln (d.h. algebraisieren!).Im Zentrum der Software-Entwicklung stehen die Erweiterung und Parallelisierung des AMG-Packetes PEBBLES. Diese Software-Packet ist so gebaut, daß es Partnern in der Forschung und in der Wirtschaft erlaubt, effiziente AMG- Lösungsmodule für ihre Zwecke herauszulösen.

Die Computersimulation vieler praktischer Probleme in der Mechanik, der Elektrodynamik, den Lebenswissenschaften etc. basiert auf mathematischen Modellen, die durch partielle Differentialgleichungen (pDgl) bzw. durch Systeme von pDgl beschrieben werden. Im Allgemeinen können diese pDgl nicht analytisch gelöst werden. Die numerische Behandlung von pDgl durch Diskretisierungsmethoden führt in der Regel auf großdimensionierte Gleichungssysteme mit mehreren Tausenden oder gar Millionen Unbekannten. Die schnelle Lösung dieser Gleichungssysteme bildet den heißen Kern aller Simulationssysteme. Die klassischen geometrischen Mehrgitterverfahren haben sich als sehr schnelle Lösungsverfahren für bestimmte Problemklassen erwiesen. Sie benötigen jedoch eine Folge von immer feiner werdenden Diskretisierungen. In kommerziellen Finite-Elemente- Programmen sind diese Diskretisierungsfolgen oft nicht realisierbar. Des Weiteren sind viele praktische Probleme geometrisch so komplex, dass ein einmal erzeugtes "grobes" Netz nicht mehr verfeinert werden kann. In diesen Fällen können Algebraische Mehrgitter-verfahren (AMG) sehr hilfreich sein. Sie starten nämlich von einem gegebenen Netz sowie dem dazugehörigen Gleichungssystem und erzeugen automatisch gröbere (kleinere) Gleichungssysteme. Folglich können AMG Methoden blackboxartig ein anderes Lösungsverfahren ersetzen, ohne dass das Anwenderprogramm groß verändert werden muss. Gerade diese Eigenschaft macht die AMG Verfahren für kommerzielle Programme außerordentlich attraktiv. Im vorliegenden Forschungsprojekt haben wir effiziente und robuste AMG Methoden für spezielle Problemklassen entwickelt. Die Lokalisierung der Ursache von Epilepsieanfällen mittels Computersimulation erfordert die Lösung von anisotropen Potentialproblemen mit vielen rechten Seiten. Unser darauf spezialisiertes AMG Verfahren wird jetzt im Programmpaket NeuroFEM in der medizinischen Forschung genutzt. Eine andere praktisch wichtige Anwendungsklasse sind die Maxwell-Gleichungen, die elektromagnetische Phänomene beschreiben. Die Maxwell- Gleichungen erfordern spezielle Diskretisierungen durch so genannte Kantenelemente. Wir haben ein neues, sehr effizientes AMG Verfahren für Gleichungssysteme, die bei derartigen Diskretisierungen mittels Kantenelemente entstehen, entwickelt. In der numerischen Strömungsmechanik sind schnelle Lösungsverfahren für die Navier- Stokes-Gleichungen gefragt. Auch hier haben wir neue AMG Methoden für spezielle gemischte Finite-Elemente- Diskretisierungen der Navier-Stokes-Gleichungen entwickelt. Insbesondere für Probleme, die in unbeschränkten Rechengebieten gegeben sind, kann die Randelementmethode (REM) sehr erfolgreich eingesetzt werden. Spezielle Approximationen der an sich voll besetzten Randelement-Matrizen erlauben die Konstruktion von fast optimalen AMG Verfahren.