Große Matrix mit vielen Nullen effizient speichern

Hallo,

ich würde gerne eine 2^16 x 2^16 Matrix effizient speichern. Die meisten Einträge (d.h. fast alle) sind Null.
Gibt es hierfür irgendwelche "fertigen Lösungen", die man schnell und ohne großen Aufwand implementieren kann?
Anschließend muss ich Matrix häufig mit Vektoren multiplizieren, gibt es hierfür auch ein besonders schnelles und effizientes Verfahren?

Vielen Dank!

otze

sparse Matrix ist dein Freund.

Es gibt einige Ansätze: http://en.wikipedia.org/wiki/Sparse_matrix
Welcher genau der ist den du brauchst, hängt von der Form deiner Matrix ab.

Gibt es denn kein fertiges Paket zum Einbinden? Solche Probleme kommen doch garantiert öfter vor, oder?

otze

Natürlich gibts das. Es gibt pakete für Python, C,C++, Matlab, Fortran, Java, C#, Haskell, Lisp, Ocaml... und auch immer mehrere. Aber hier bist du im Mathebereich da werden Mathefragen beantwortet ;). Wir Glaskugeln hier keine Matrixformen und Programmiersprachen.

mngbd

Donnie666 schrieb:

Gibt es hierfür irgendwelche "fertigen Lösungen", die man schnell und ohne großen Aufwand implementieren kann?

Zuerst einfach eine Hashtabelle versuchen. Vielleicht reicht das ja.

Vielleicht hilft dir das Buch "Numerical Recipes"

und die dazugehörige Software weiter.

Gruß,

Andreas

Walli

Wie bereits gesagt, kommt es sehr auf die Form der Matrix an und darauf, was Du damit machen willst. Eine Diagonalmatrix wird man z.B. immer in ein simples Array packen, während man bei einer zufällig besetzten Matrix je nach Anwendungsfall verfährt. Schau Dir die Sparse-Implementierungen von boost::ublas an, da bekommst Du einen kleinen Überblick dessen, was gemacht wird. Wenn es auf Performance und ggf. Parallelisierung ankommt, dann solltest Du vielleicht eher mal PETSc anschauen.