Bau gewaltige Matrix zu aufwendig -> abhilfe?

Hallo,

ich habe das Problem dass meine Erstellung meiner Matrix einfach zu aufwendig ist.
Was ich brauch ist ein Matrix-Vektor Produkt. Dazu wollte ich eine Matrix aufbauen die durchaus von Dimensionen 100000 mal 100000 sein kann. Ich lasse "dummerweise" einfach ein 2D Array mit eben sovielen Nullen füllen und später einfach einzelne werte setzen in der Matrix. Wichtig ist dass nur ca. 1000 Stellen der Matrix mit etwas ungleich Null belegt sind. Natürlich sprengt diese Matrix meinen Speicher und sonst was alles.
Jetzt weiß ich allerdings nicht weiter. Sollte ich vielleicht nur die belegten werte irgendwie speichern? Hat jemand irgendwelche ideen wie ich an eine Problemlösung rankomme?

Für jede Hilfe bin ich dankbar!

Danke

eine Möglichkeit wäre vielleicht 2 Vektoren zu erstellen wo im ersten nur die Zeilen gespeichert werden die einträge haben und analog dazu im zweiten dann nur den Index und den Wert in dieser Zeile. Damit würde ich nur die besetzten Elemente haben...
vielleicht was besseres?

viele werte wiederholen sich sehr oft.
Also z.B eine 6 wiederholt sich durchaus 100 mal....
ginge vielleicht sowas wie auf die besetzen werte Pointer zu setzen und damit nur Arrays aus Pointern zu haben - weil mit der idee von vorhin würden die vektoren eine Länge von 10000 haben können.???

akari

Hallo

auf jedenfall ist die Idee aus dem zweiten Post mit vector oder besser noch einer map (Zellkoordinaten nach Zellwert) effizienter.
Ob sich eine Pointerliste auf gleichwertige Zellen lohnt muß nochmal überdacht werden, denn auch die Pointer brauchen ja 4Byte Speicher, bei Integer-Werten lohnt sich das nicht.

bis bald
akari

danke ...könntest du vielleicht ein wenig näher auf die idee mit der Map eingehen? Hab ich so noch net ganz geschnallt...danke :p

akari

Hallo

Zum allgemeinen Verständniss von map siehe den Artikel im Forenmagazin.

Ich empfehle so ein Aufbau

// Struktur der Zellkoordinaten
struct CellCoord
{
  int x;
  int y;
};

// Maptyp für Integer-Werte sortiert nach deren Zellkoordinaten
typedef std::map<CellCoord, int> MatrixMap;

bis bald
akair

Braunstein

Hallo,

In diesem Buch
http://www.informatik.hs-bremen.de/~brey/stlb.pdf
Kapitel 9.4 wird die Implementierung ein dünn besetzten Matrix beschrieben.

Werner Salomon

Hallo testo,

ich glaube dieser Thread könnte auch noch hilfreich sein.

Gruß
Werner

hjdt

Mal ganz ehrlich, Matrix-Vektor- oder Matrix-Matrix-Operationen sind auf einem Rechner mit dieser Dimension immer ineffizient, da lässt sich nicht dran rütteln.
Von der Genauigkeit der Ergebnisse (die wohl in vielen Fällen sehr ungenau oder sogar falsch sein werden) wollen wir mal gar nicht reden. Effizienz wird wohl nur durch Parallelisierung erreicht werden (Stichwort MPI) und die Genauigkeit bzw. die Einschließung eines Ergebnisses durch verifizierende Algorithmen (Stichwort XSC). Auf einem 512-Knoten Cluster dauert die ganze Berechnung (Matrix-Matrix) ca. 1 Std.

Danke euch vielmals!
Der Link zu dem pdf ist echt super! Danke ich hoffe ich werde fündig.

Ja mit den Parallelrechnern stimmt schon. Aber durch performante implementierung kann man durchaus schnelligkeit gewinnen. Und wer weiß ...möglicherweise steig ich zusätzlich noch auf Parallelrechner um

Deswegen der Thread und die Frage.

Danke für die Antworten.

Bau gewaltige Matrix zu aufwendig -&gt; abhilfe?

Bau gewaltige Matrix zu aufwendig -> abhilfe?