Verfahren zur Lösung eines linearen Gleichungssystems mit einer dünnbesetzten Koeffizientenmatrix

[MAXtrix (Gast)]

Guten Abend!

Vielleicht hat ja einer von euch ein Verfahren im Kopf, welches ich für 
das Lösen von dünnbesetzten Matrizen verwenden kann.

Im Moment speichere ich die gesamte Koeffizientenmatrix ab und löse die 
Gleichung mit dem Gauss-Seidl Verfahren. Jedoch explodiert bei mir 
natürlich ab einer gewissen Größe des LGS die Rechenzeit.

Meine Matrix ist eine Bandmatix, bei der die Hauptdiagonale, die 1ste 
obere und 1ste untere Nebendiagonale, sowie jeweils die zb. 5te obere 
und untere Nebendiagonale (hängt von der Anzahl der Knotenpunkte für die 
Diskretisierung ab) besetzt ist.

Ich habe bereits ein wenig gesucht, jedoch immer Beispiele für 
tridiagonale Matrizen gefunden, in denen nicht erwähnt wurde, ob die 
angegebenen Algorithmen auch für Bandmatrizen zu verwenden sind.

Danke für eure Hilfe!
lg

[Na Sowas (Gast)]

Ja. Die Loesung hoert sich noch viel duemmer an. Koeffizienten, die Null 
sind muss man gar nicht erst anfassen. Einfacher : man muss eigentlich 
nur die Zellen ungleich Null miteinander multiplizieren.

[Johann L. (gjlayde)]

MAXtrix schrieb im Beitrag #2781242:

> "Verfahren zur Lösung eines linearen Gleichungssystems mit einer
> dünnbesetzten Koeffizientenmatrix"

Hat die Matrix sonstige Eigenschaften? Positiv definit? Hermitesch? 
Cholesky-Zerlegung? LR-Zerlegung?

GNU GSL, siehe "TB triangular band":

http://www.gnu.org/software/gsl/manual/html_node/BLAS-Support.html

Oder LAPACK?

http://www.netlib.org/lapack/explore-html/de/d52/group___g_b.html

"Direct Solvers for Sparse Matrices":

http://web.eecs.utk.edu/~dongarra/etemplates/node388.html

[Andreas S. (Firma: Schweigstill IT) (schweigstill)]

Während meines Studiums waren die Herren Hackbusch und Brokate die 
großen Experten in dieser Thematik. Vielleicht findest Du entsprechende 
Publikationen der beiden.

[Purzel (Gast)]

Man kann natuerlich fertige Packages bemuehen. Oder selbst nachdenken. 
Erstens sollte man die sinnlose Adressiererei der Elemente wegmachen.
Denn das Element[x,y] zu adressieren bedeutet eine Multiplikation und 
eine Addition. Wenn man nun in einer Spalte 9995 Nullen und 5 Werte hat, 
so sind die 9995 Zugriffe sinnlos.

Wenn nun der Anfang eine 10 diagonale Matrix ist, so wird ein iterativer 
Algorithmus, der zu einer eindiagonalen Matrix fuehrt nie mehr Elemente 
pro Spalte und Zeile haben wie diese 10. Denn sonst wuerden ja 
Kopplungen eingefuehrt, die vorher nicht da waren. Nein ?