Das Demonstrationsbeispiel
Um die Eigenschaften der Lösung linearer Gleichungssysteme mit dünn besetzter Koeffizientenmatrix zu demonstrieren, muss ein System mit einigen tausend Gleichungen betrachtet werden. Hier soll ein typisches FEM-Gleichungssystem verwendet werden. Das nebenstehend zu sehende Finite-Elemente-Modell der Brücke über den Nord-Ostsee-Kanal bei Rendsburg führt auf ein (im Vergleich mit typischen FEM-Modellen eher kleines) Gleichungssystem mit 4482 Unbekannten, das allerdings genügt, um die Vergleiche der Speicherungsvarianten durchzuführen.
Das Finite-Elemente-Modell liegt als Datei im Femset-Format vor. Für die Demonstration der "Sparse matrix"-Variante wird mit Matlab gearbeitet, weil diese Speicherung in Matlab sehr effektiv unterstützt wird. Die Speichervarianten "Band" und "Skyline" sind im Programm WFemset realisiert, in dem Speicherung und Ablauf der Berechnung anschaulich visualisiert werden.
"Sparse" und "Voll"
Mit dem Matlab-Femset-Interface kann das Gleichungssystem in Matlab erzeugt werden. Das nebenstehende Matlab-Script zeigt in Zeile 4 das Einlesen des Berechnungsmodells von der Datei, in Zeile 6 wird das Gleichungssystem aufgebaut (beides wird mit Femset-Routinen erledigt). Weil Femset die Koeffizientenmatrix als symmetrische Bandmatrix abliefert, wird diese in Zeile 8 in eine Matlab-Sparse-Matrix umgesetzt.
Schließlich wird (Zeile 11) das Gleichungssystem mit dem Matlab-"Backslash-Operator" gelöst. Hier wird nur das Belegungsmuster als Graphik ausgegeben (Zeile 10) und die für die Behandlung des Gleichungssystems erforderliche Zeit gemessen (Zeile 12).
Um eine Vorstellung zu bekommen, welcher Aufwand durch die drei Strategien "Band", "Skyline" und "Sparse" vermieden wird, ist in Zeile 14 noch die Umformung in eine voll besezte Matrix vorgesehen, anschließend wird das Gleichungssystem noch einmal mit dieser Matrix gelöst. Auch hier wird die Zeit gemessen.
Nachfolgend sieht man rechts das Belegungsmuster der "Sparse matrix". Von den 44822 = 20 088 324 Matrixelementen sind nur 82 678 von Null verschieden (0,4%). Im Command Window findet man die Zeiten, die für die Behandlung der 
Gleichungssysteme erforderlich waren:
"Band" und "Skyline"
Diese beiden Speichervarianten können mit dem Programm WFemset (zum Download verfügbar) demonstriert werden.
Zunächst wird mit der Bandmatrix-Strategie gearbeitet:
Datei | Öffnen | Datei Rendbrem.dat öffnen | Berechnen | Rechnung starten (Bandmatrix).
Man sieht den Aufbau des Gleichungssystems und bei der Lösung den Fortschritt (Abarbeitung der einzelnen Gleichungen entlang des Bandes). Der nebenstehende Bildschirm-Schnappschuss zeigt das Protokoll der Berechnung und die Struktur des Gleichungssystems nach der Dreieckszerlegung nach Cholesky (weil die Knotennummerierung in dem Berechnungsmodell annähernd optimal ist, hat die Koeffizientenmatrix eine sehr schmale Bandweite).
Nun kann sofort die Rechnung nach der Skyline-Methode ausgeführt werden:
Berechnen | Rechnung starten (Skyline).
Die Lösung des Gleichungssystems erfolgt in deutlich kürzerer Zeit, man erkennt, dass die Skyline offensichtlich an den meisten Stellen noch deutlich schmaler ist als das Band. Während der Berechnung sieht man, wie sich die "Schornsteine" der Skyline nach und nach mit Nicht-Null-Elementen auffüllen.
Fazit
- Für große lineare Gleichungssysteme kommt man bei Speicherung der Koeffizientenmatrix als voll besetzte Matrix sehr schnell an die Grenzen der Speicherkapazität, viel eher aber noch an die Grenzen akzeptabler Rechenzeiten für die Lösung (diese Aussage gilt, weil die Rechenzeit proportional zur dritten Potenz der Anzahl der Gleichungen steigt, auch für sehr schnelle Computer, auch wenn sich dort die Grenzen verschieben).
- Die klassische Bandspeicherung reduziert die erforderlichen Rechenzeiten deutlich, ist aber gegenüber den beiden nachfolgend genannten Varianten auch dann nicht konkurrenzfähig, wenn eine Optimierung der Bandweite vor der Lösung des Gleichungssystems vorgenommen wird.
- Die beiden Speichervarianten "Skyline" und "Sparse" nutzen die Tatsache, dass das "Fill-in" (Erzeugen von Nicht-Null-Elementen auf Positionen, auf denen in der Ausgangsmatrix Nullen standen) vorhergesagt werden kann, wobei die "Skyline"-Methode durch Operationen entlang von geschlossenen Speicherbereichen ("Schornsteine") der effektiven Programmierung entgegenkommt, die "Sparse matrix"-Strategie dagegen tatsächlich das minimal mögliche "Fill-in" realisieren kann. Beide Verfahren können durch vorab durchzuführende Zeilen- und Spaltentausch-Operationen ("Fill-in-Minimierung") erheblich beschleunigt werden.
- Die "Sparse matrix"-Speicherung ist die ideale Variante für die Berechnung des Gleichungssystems mit iterativen Verfahren, weil die Matrix bei diesen Verfahren nicht verändert wird. Diese Aussage gilt uneingeschränkt, auch wenn gerade das hier benutzte Demonstrationsbeispiel den iterativen Lösungsverfahren erhebliche Probleme bereitet (siehe "Testrechnungen mit iterativen Verfahren (2)").
Schließlich soll noch gezeigt werden, was mit den Gleichungssystemen berechnet wurde. Es ist die Verformung der Brücke unter dem besonders kritischen Lastfall "Vollbremsung eines Zuges".
Im nebenstehenden Bild sind die berechneten 4482 Verformungsparameter an den Elementknoten berücksichtigt, wobei die Verschiebungen (im Verhältnis zu den sonstigen Abmessungen) um das 200-fache vergrößert dargestellt sind (gestrichelt dargestellt ist im Hintergrund das unbelastete System).
Das abgebildete Matlab-Script und die daraus aufgerufenen Functions und DLLs und die Modell-Datei sind zum Download verfügbar: Sparsetest2.m, finmod_m.dll, syswbc_m.dll, SymBand2Quad.m, SymBand2Sparse.m, Rendbrem.dat.
Über eine eigene Seite kann das Programm WFemset bezogen werden.
