Geringster Speicherbedarf: "Sparse-Matrix-Speicherung" und "Fill-in-Problem"
Die allgemeine "Sparse Matrix"-Speicherung, wie sie z. B. in Matlab realisiert ist, geht noch einen Schritt weiter: Es werden nur die Nicht-Null-Elemente und zu jedem Element das zugehörige Indexpaar (Position des Elementes in der Matrix) gespeichert (die Menge aller Indexpaare der Nicht-Null-Elemente wird "Besetzungsstruktur" der Matrix genannt). Diese Variante ist natürlich ideal, wenn sich die "Besetzungsstruktur" der Matrix während des Berechnungsprozesses nicht ändert (wie z. B. bei den Iterationsverfahren zur Lösung von Gleichungssystemen oder beim "Incomplete Cholesky"-Verfahren).
Beim Cholesky-Verfahren ist diese Speichervariante weitgehend gleichwertig mit der oben beschriebenen "Skyline"-Methode: Das "Fill-in" sorgt für zusätzlich erforderliche Speicherplätze während des Algorithmus und der erforderliche Aufwand ist vergleichbar. Bei der "Skyline"-Variante wird das "Fill-in" gewissermaßen vorausgedacht, und es sind von vornherein zusammenhängende Bereiche vorhanden (die vertikalen "Schornsteine", die als Vektoren gespeichert werden), was einer effektiven Programmierung entgegenkommt. Andererseits sollte natürlich am Start des Cholesky-Verfahrens für eine "Sparse matrix" die Prognose für die erforderlichen Speicherbereiche stehen, die dann in einem Schritt auch organisiert werden (auf keinen Fall sollte jedes beim "Fill-in" entstehende Element eine Speicherplatzanforderung auslösen), und damit sind diese beiden Speichervarianten weitgehend gleichwertig.
In Matlab ist diese Speichervariante für zahlreiche Operationen verfügbar und außerordentlich effektiv realisiert.
Das folgende kleine Matlab-Script demonstriert die "Sparse Matrix"-Speicherung und das "Fill-in" an einem kleinen Beispiel:
In der Zeile 3 wird das FEM-Berechnungsmodell der oben dargestellten Brückenkonstruktion von der Datei Fof.dat eingelesen, in Zeile 5 wird daraus das lineare Gleichungssystem mit Matlab-Femset erzeugt.
In Zeile 7 wird die (symmetrische und postiv definite) Koeffizientenmatrix in das Matlab-"Sparse Matrix"-Format umgewandelt, in Zeile 9 wird die Cholesky-Zerlegung ausgeführt. Rechts sieht man die beiden Belegungsmuster der (symmetrischen) Ausgangsmatrix und der nach Cholesky erzeugten Rechtsdreiecksmatrix. Deutlich sieht man, dass sich die "Schornsteine" (wie oben beim Skyline-Verfahren beschrieben) weitgehend gefüllt haben.
Die Vorteile der beschriebenen Speichervarianten zeigen sich natürlich erst bei großen Gleichungssystemen. Dies wird auf der Seite "Band", "Skyline", "Sparse" und "Voll" demonstriert.
Verfahren zur Reduzierung des Fill-in können den Aufwand drastisch verringern, siehe hierzu "Reduzierung von Bandweite und Fill-in".
|