(4.111) |
Um gutes Laufzeitverhalten zu gewährleisten, muss die Datenstruktur so aufgebaut sein, dass der verwendete Gleichungslösungsalgorithmus effizient darauf zugreifen kann. Dabei ist es wichtig, dass beim Zugriff auf Matrixelemente keine Verzögerung durch langes Suchen entstehen und unnötige Operationen mit Null-Einträgen vermieden werden. Mit dem MCSR-Format kann eine MatrixVektor-Multiplikation sehr effizient durchgeführt werden, wodurch es sich für die Anwendung beim Konjugierten Gradientenverfahren (siehe unten) besonders eignet.
Anmerkung: Theoretisch wäre eine solche MatrixVektor-Multiplikation auch ohne vorherige Assemblierung der Systemmatrix, sondern direkt als Summierung über die Elementmatrizen möglich. Diese Methode kommt mit minimalem Speicherbedarf aus, hat aber einen ungleich höheren Rechenaufwand. Es können jedoch Teilgebiete des Gitters zu Teilmatrizen zusammengefasst werden, und die MatrixVektor-Multiplikation getrennt über diese Teilmatrizen ausgeführt und anschließend aufsummiert werden. Dieser Algorithmus kann zur Parallelisierung der Finite Elemente Methode ausgenutzt werden, indem man jedem Teilbereich einen eigenen Prozess zuordnet. Die Aufteilung sollte so geschehen, dass die Anzahl der Kopplungen zwischen den Teilbereichen minimal ist, damit wird auch die Kommunikation zwischen den Prozessen minimiert.
Neben dem Konjugierten Gradientenverfahren wird auch das Gauß'sche Eliminationsverfahren zur Lösung des Gleichungssystems herangezogen. Dafür benötigt man ein Matrixformat, das in jeder Zeile zwischen dem ersten und dem letzten von Null verschiedenen Eintrag einen Speicherplatz reserviert, da diese Einträge später bei der Matrixfaktorisierung verwendet werden. Bei einer symmetrischen Matrix reicht es aus, wenn vom ersten von Null verschiedenen Element bis zur Diagonale Speicherplatz reserviert wird. Man spricht dabei von einer hüllenorientierten Struktur, deren Speicherbedarf von den Bandbreiten der einzelnen Zeilen abhängig ist und im Regelfall einem Vielfachen des MCSR Speicherbedarfs entspricht. Eine Reduktion der mittleren Bandbreite lässt sich durch Umordnen der Knotennummerierung erzielen, was in der Matrix ein Vertauschen von Zeilen und Spalten bewirkt (und natürlich auch in den und Vektoren). Dafür haben sich das Cuthill-McKee-Verfahren (CM) bzw. das Reverse-CuthillMcKee-Verfahren (RCM) etabliert [117]. Die Wirkungsweise des RCM Verfahrens ist in Abb. 4.5 anhand eines Beispiels dargestellt.
Wie weit die mittlere Bandbreite einer Matrix durch Umsortieren minimiert werden kann, hängt nicht nur vom verwendeten Verfahren ab, sondern in viel stärkerem Ausmaße von der Struktur der Matrix (bzw. des Gitters) selbst. Beispielsweise lassen sich bei der dreidimensionalen Widerstandsberechnung bei sehr langen und dünnen Leitungen sehr geringe mittlere Bandbreiten (60 und darunter) erreichen.
Als erster Schritt wird die Systemmatrix in ein Produkt aus einer unteren und einer oberen Dreiecksmatrix faktorisiert:
(4.113) | ||
(4.114) |
Für die Berechnung von Kapazitäten, Widerständen, oder transienten Vorgängen muss oft ein System mit gleicher Matrix aber verschiedener rechter Seite gelöst werden. In diesem Fall braucht die (langsame) Faktorisierung nur beim ersten Mal durchgeführt werden und die Lösung kann bei jedem weiteren Schritt sehr effizient mittels Vorwärtseinsetzen und Rückwärtseinsetzen berechnet werden.
Zur weiteren Reduktion des Speicherbedarfs kann die Assemblierung und Elimination kombiniert werden: In diesem Fall wird die Systemmatrix nicht in Teilmatrizen aufgespalten sondern es wird komplett mit allen Randknoten gearbeitet. Diese Methode bietet sich besonders an, wenn man nicht an einer Verteilung des Potenzials im Inneren des Simulationsgebietes, sondern lediglich an einer Kapazitäts- oder Widerstandsmatrix interessiert ist. Sobald sämtliche Elemente, die einen bestimmten Gitterknoten gemeinsam haben, assembliert worden sind, kann dieser Knoten aus dem Gleichungssystem eliminiert werden. Randknoten, die zu einer Elektrode gehören, können, da sie auf dem selben Potenzial liegen, ebenfalls zusammengefasst werden. In diesem Fall erspart man sich die Rücksubstitution und erhält direkt die gewünschte (Kapazitäts- bzw. Leitwert-) Matrix.
Das konjugierte Gradientenverfahren (CG) ist eine sehr häufig verwendete Methode lineare Gleichungssysteme iterativ zu lösen. Es zeichnet sich besonders dadurch aus, dass es nahezu keinen zusätzlichen Speicherplatz benötigt und im Regelfall mit deutlich weniger Rechenoperationen auskommt als die Gauß'sche Elimination. Allerdings handelt es sich bei der erhaltenen Lösung nur um eine Näherung, da die Iteration abgebrochen wird sobald ein Konvergenzkriterium erfüllt ist4.8. Voraussetzung ist eine symmetrische und positiv definite Systemmatrix. Der Rechenaufwand des CG-Verfahrens ist proportional zur Wurzel der spektralen Konditionszahl der Matrix, das ist das Verhältnis zwischen größtem und kleinstem Eigenwert.
Näher soll im Rahmen dieser Arbeit nicht auf das CG-Verfahren eingegangen werden--es sei an dieser Stelle auf die ausführliche Darstellung in [118] verwiesen.
Zur Beschleunigung der Konvergenz besteht die Möglichkeit der Vorkonditionierung. Anstatt (4.112) wird das System
(4.115) |
Der CG-Algorithmus kann auch erweitert werden, sodass für mehrere rechte Seiten ohne großen zusätzlichen Aufwand gleichzeitig Lösungen berechnet werden können [121,122].