Eigenwerte einer sehr grossen Matrix
-
Ich weiß, die Antwort lautet TNT oder LAPACK, aber die mir gegebene Matrix ist bissel größer als 20'000x20'000. Bei Double macht das 20'000x20'000x8Byte > 3GByte.
Die Matrix ist jedoch der symmetrisch, sehr dünn besiedelt (über 90% der Werte sind Nullen), die Hauptdiagunale besteht nur aus Einsen, alle Werte sind im Bereich zwischen 0 und 1 (also real und positiv) und desweiteren liegt die Matrix nicht als Double sondern als Float vor.
Weiß jemand wie man diese Eigenschaften nutzen kann um das Problem zu Lösen???
-
Schau mal in Numerical Recipes nach.
Da gibt es glaube ich Algorithmen für Matrixen mit
vielen Null-Werten (Sparse Matrizen)
-
Lapack bietet Datenstrukturen und Algorithmen fuer duenn besetzte Matrizen.
-
Dein Freund sind die Unterraumverfahren. (So ähnlich wie CG oder GMRES für Gleichungssysteme).
Ganz viel Theorie gibts auf dieser Seite dazu:
http://www.tu-harburg.de/ins/download/skripte.html(Summer school on
Iterative Projection methods for sparse linear systems and eigenproblems)Lapack alleine wird dir nicht helfen, weil es da imho keine fertigen Löser für sparse Eigenprobleme gibt.
Ich hoffe, du brauchst nur ein paar Eigenwerte/-vektoren (z.b. die größten oder kleinsten Eigenwerte). Stichworte: Jakobi-Davidson-Verfahren. Lanzcos-Verfahren (schreibt man den so?), Arnoldi-Verfahren.
-
knivil schrieb:
Lapack bietet Datenstrukturen und Algorithmen fuer duenn besetzte Matrizen.
So wie ich das sehe gibt es keine Datenstrukturen für dünnbesetzte Matrizen (wie z.B. Compressed Sparse Column) in Lapack.
Ich hab jetzt mit Lapack und der Datenstruktur SSP (Float32, halbe Matrix) gearbeitet. Dies viertelt meine zuvor angesetzten 3GByte auf unter 1GByte. Laufen tut das Programm schon, fragt sich nur wie lange es braucht ...
Vielen Dank an Alle.
Sebastian
-
Mach es mit Sparse-Matrizen, dafür sind die da. Wenn man sich ein Gigabyte mit einer so kleinen Matrix vollpackt, dann sollte man schon einen guten Grund dafür haben. Ich würde mir da mit PETSc und SLEPc was basteln. Selbst wenn Du das nicht parallel fährst sind die meisten Sachen da echt fix implementiert. Und Du kannst mal schnell verschiedene Sachen (Lanczos, Arnoldi etc.) ausprobieren.
-
LaPack hat 11,5h gebracht für meine dünnste Matrix. Da mein Chef wohl doch vor hat mehr als doch nur 5 mal das Programm rechnen zu lassen muss ich es wohl doch erheblich beschleunigen. Ich werde es, wie von Walli vorgeschlagen, mit PETSc und SLEPc versuchen. Für weiter Vorschläge habe ich weiterhin ein offenes Ohr.
Gruß Sebastian
-
Die GNU Scientific Library (GSL) bietet sicherlich die Datenstrukturen und Löser für deine Probleme:
http://www.gnu.org/software/gsl/