Eigenwert system

[Eeth]

Hallo zusammen,

ich hab gerade ein kleines Problem:

Folgendes Eigenwertsystem sei zu lösen (* = Multiplikation):

D^(-1/2) * (D - W) * D^(-1/2) * x = lambda * x

Mit D = Diagonalmatrix und W = Gewichtungsmatrix mit reellen Zahlen und beide sind in der Form NxN

(D^(-1/2) * (D - W) * D^(-1/2)) = A = Sparse & Symmetrisch.

Problem: N kann > 200000 werden, was es schier unmöglich macht das ganze mit bekannten Eigenvalue Lösungsverfahren zu bestimmen. (Speicher! und ich hab das ganze im C++ und würde nur ungern Matlab anbinden, wobei ich mir nichtmal sicher bin ob Matlab das packt).

Gibt es iterative Lösungsverfahren welche ich hier verwenden kann?
Würde Gauß-Seidel hier funktionieren wenn ich das ganze Lösungssystem aufstell? Ich kenne immer die exakten Werte an einer Position, bzw. kann diese sehr schnell berechnen.

Bin leider kein Mathematiker und werde auch nie einer sein, also wenn ich Informationen vergessen habe, fragt danach

Viele liebe Grüße und Thx

Eeth

PS: Für die, die es interessiert: Ich versuche gerade "Normalized Cuts" zur Bildsementierung zu implementieren. Will keinen existierenden Code verwenden, weil ich meinen Code direkter und einfacher manipulieren kann.

 

[voelkerballtier]

ich bin da leider auch kein experte, aber ein paar anmerkungen:

Eigenwert-verfahren (QR) sind doch immer iterativ, dachte ich?
Brauchst du wirklich das komplette System oder zB nur den größten EW?
Hast du schon mal Algorithmen extra für Sparse Matrizen angeschaut? Bzw. wie "sparse" id A bei dir? siehe http://en.wikipedia.org/wiki/Lanczos_algorithm gibt garantiert etliche c++ implementationen.
Ausserdem wichtig sind Symmetrien in A - sofern da welche vorhanden sind kann deren ausnutzung den numerischen aufwand erheblich verringern, dazu braucht es aber schon etwas mehr Mathematik.
Am wichtigsten ist erstmal (falls noch nicht geschehen) das ausnutzen der sparse-heit.

€: kurzes googlen brachte noch folgenden link: http://www.comp-phys.org/software/ietl/

 

[Eeth]

Najo... habmich glaub falsch ausgedrückt oder ich versteh was nicht.
Dass die Verfahren alle Iterativ sind ist mir klar. Aber sie setzen doch alle vorraus, dass die komplette Matrix A (bzw. D und W) im Speicher gehalten wird?

Genau das is mein Problem

 

[FORYOUITERRA]

gerade mal nach deinen thema gegoogled: unter den ersten treffern befindet sich
http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf
da wird vorgeschlagen die lancosz methode zu nutzen wie völkerballtier schon sagte.

 

[Heimatloser]

Es reicht wenn du immer eine Zeile auswerten kannst.
Der erste Iterationsschritt wertet dann N Zeilen aus verändert N Werte.
zB Gauss-Jacobi Verfahren wenn ich mich nicht irre
ist aber sicher nicht die eleganteste lösung, aber wenn du nur code hacken willst die einfachste

 

[Eeth]

gerade mal nach deinen thema gegoogled: unter den ersten treffern befindet sich
http://www.cs.berkeley.edu/~malik/papers/SM-ncut.pdf
da wird vorgeschlagen die lancosz methode zu nutzen wie völkerballtier schon sagte.

hi ja, ist mir bewusst. Das ist das orginal Paper von den Jungz Übrigens ein sehr elegantes Paper und jetzt der Fluch der beiden, da sie immer an diesem gemessen werden

Ich hab glaub einfach die Methode nicht richtig verstanden. (Lanzcos).
Werd mich da jetzt mal tiefer einlesen in das Verfahren und hoffentlich selbst auf den Trichter kommen.

Ansonsten bleibt mir noch die möglichkeit nen genetischen Algorithmus zur Optimierung anzusetzen. Ist eigentlich ein schönes Problem dafür, da man jede Partitionierung tatsächlich als Binären Vektor darstellen kann und somit Codierung/Mutation/etc.. sehr intuitiv sind.

€: Ich möchte eben nicht zuviel Zeit für diesen Segmentierungsschritt verschwenden, da mein eigentliches Problem Klassifizierung ist.