Matrix invertieren (numerisch)
Philipp Kraus
ich arbeite im Moment mit PHP und habe dort eine Matrixklasse
geschrieben. Nun m�chte ich auch die M�glichkeit haben die Matrix zu
invertieren. Im Normalfall w�rde ich LAPack daf�r verwenden, leider
habe ich unter PHP diese M�glichkeiten nicht, so dass ich das eben
h�ndisch machen muss.
Die Matrizen sind alle reell. Welche Algorithmen muss ich verwenden, um
ein volle / sparse Matrix zu invertieren, so dass es numerisch stabil
bleibt?
Danke
Phil
Knut
> Hallo,
>
> ich arbeite im Moment mit PHP und habe dort eine Matrixklasse
> geschrieben.
Ja, das ist ziemlich wichtig. Wo kann man diese Klasse finden?
Philipp Kraus
im Moment auf meiner Festplatte :-P
Wie würde man denn den Algorithmus zur Inversion angehen?
Phil
Knut
Der ist extrem simpel, und dass gab es gerade (!) auch hier vor
kurzem auch neben aller Algorithmik in extrem schnellem numerischen
Metacode (als auch in lauffägigem c und c++ oder c# code). Leider
bin ich jetzt zu erschöpft um das für dich zu suchen, im ernst...
Sicher oder hftl werden andere da morgen helfen... "Wesentlich" ist,
dass die Adjunkte für die Lösung gewissermassen definiert ist...
Ernst.Sauer
> Hallo,
>
> ich arbeite im Moment mit PHP und habe dort eine Matrixklasse
> invertieren. Im Normalfall würde ich LAPack dafür verwenden, leider habe
> ich unter PHP diese Möglichkeiten nicht, so dass ich das eben händisch
> machen muss.
> Die Matrizen sind alle reell. Welche Algorithmen muss ich verwenden, um
> ein volle / sparse Matrix zu invertieren, so dass es numerisch stabil
> bleibt?
>
> Danke
>
> Phil
>
>
Ich zitiere Roland Franzius, der hat vor kurzem geschrieben:
"
A^-1 = 1/det(A) Adj (A), wobei die Adjunkte Adj(A) die transponierte
einer Matrix mit Matrixelementen der Determinanten_ij ist, die durch
Streichen der Zeile i und der Spalte j entstehen.…
"
(beachte die Vorzeichen).
Gruß
E.S.
Ernst.Sauer
>
> ich arbeite im Moment mit PHP und habe dort eine Matrixklasse
> invertieren. Im Normalfall würde ich LAPack dafür verwenden, leider habe
> ich unter PHP diese Möglichkeiten nicht, so dass ich das eben händisch
> machen muss.
> Die Matrizen sind alle reell. Welche Algorithmen muss ich verwenden, um
> ein volle / sparse Matrix zu invertieren, so dass es numerisch stabil
> bleibt?
>
> Danke
>
> Phil
>
>
Als Variante kannst Du auch ein lineares Gleichungssystem
mit n rechten Seiten lösen.
Die rechten Seiten sind die Spalten der Einheitsmatrix.
Die Ergebnisvektoren sind die Spalten der Kehrmatrix.
Gruß
E.S.
Gus Gassmann
Es spielt sicher eine Rolle, wie gross deine Matrizen sind. Im Ganzen
hast du dir hier einiges vorgenommen. Ich würde mit Suhl und Suhl
anfangen (U. Suhl and L. Suhl, Computing sparse LU-factorizations for
large-scale linear programming bases, ORSA J. Comput. 2(1990)325-335).
Das ist zwar nicht mehr auf dem neuesten Stand der Dinge, aber als
Einstieg sollte es dennoch dienen.
Knut
> Welche Algorithmen muss ich verwenden
Am besten einen, der schon funktiniert, Z.B.
ftp://garbo.uwasa.fi/pc/c-lang/matrx042.zip
Da drin ruft mat_inv( a ) mat_backsubs1(...)
MATRIX mat_backsubs1( A, B, X, P, xcol )
MATRIX A, B, X, P;
int xcol;
{
int i, j, k, n;
double sum;
n = MatCol(A);
for (k=0; k<n; k++)
{
for (i=k+1; i<n; i++)
B[(int)P[i][0]][0] -= A[(int)P[i][0]][k] * B[(int)P[k][0]][0];
}
X[n-1][xcol] = B[(int)P[n-1][0]][0] / A[(int)P[n-1][0]][n-1];
for (k=n-2; k>=0; k--)
{
sum = 0.0;
for (j=k+1; j<n; j++)
{
sum += A[(int)P[k][0]][j] * X[j][xcol];
}
X[k][xcol] = (B[(int)P[k][0]][0] - sum) / A[(int)P[k][0]][k];
}
return (X);
}
Philipp Kraus
soweit ich mich aber erinnere ist das Problem die Determinante zu
bestimmen, da das algorithmisch aufwändig ist und
Divisionen numerisch immer bedenklich sind bzw. eben die Determinante
auch existieren muss. Gerade bei sparse Strukturen
halte ich das nicht für sinnvoll.
Philipp Kraus
Hier verlagert sich doch nur das Problem, denn dann muss ich das LGS
auch numerisch lösen.
Bei sparse bzw großen Matrizen brauche ich eben die Numerik für die Lösung
Phil
Philipp Kraus
Eigentlich war das Stichwort die LU Zerlegung, ich erinnere mich, dass
ich das mal gemacht habe.....
Danke für den Buchtipp zum nachlesen
Phil
Philipp Kraus
> Philipp Kraus schrieb:
>
>> Welche Algorithmen muss ich verwenden
>
> Am besten einen, der schon funktiniert, Z.B.
> ftp://garbo.uwasa.fi/pc/c-lang/matrx042.zip
Danke das hilft schon mal sehr weiter
Phil
Ernst.Sauer
Ja klar, aber für das Lösen linearer Gleichungssysteme findest
Du doch genügend Quellen und kannst Dir die Methode wählen,
die für Dein Problem am geeigneten ist.
Fertige Programme für die Berechnung der Kehrmatrix gibt es
natürlich auch: z.B. "Numerical Recipes in C".
Alois Steindl
Die inverse Matrix wird eigentlich sehr selten wirklich benötigt: Zur
Lösung von Gleichungssystemen reicht eine LU-Zerlegung und ist meistens
viel effizienter und sparsamer, speziell bei dünn besetzten Matrizen.
Alois
Knut
> Noch eine Bemerkung:
> Die inverse Matrix wird eigentlich sehr selten wirklich ben�tigt: Zur
> L�sung von Gleichungssystemen reicht eine LU-Zerlegung und ist meistens
> viel effizienter und sparsamer, speziell bei d�nn besetzten Matrizen.
Na klar.
Aber er will ja eine Klasse schreiben.
Das ist wie wenn du eine Formelsammlung herausgibst.
Philipp Kraus
Das ist mir bekannt. Bei der LU Zerlung erhalte ich ja bei der
Rücksubsitution den Vektor, aber ich muss jeder (!) Matrixoperation in
PHP selbst schreiben, denn wie schon gesagt, PHP kennt so etwas nicht.
Philipp Kraus
Ich habe die NRs hier, aber in PHP sieht das schon wesentlich anders
aus z.B. existiert keine 2D Arraystruktur unter PHP und grade Zeilen-
bzw Spaltenoperationen muss ich schon komplett selbst implementieren
Knut
> Ich habe die NRs hier, aber in PHP sieht das schon wesentlich anders
> aus z.B. existiert keine 2D Arraystruktur unter PHP und grade Zeilen-
> bzw Spaltenoperationen muss ich schon komplett selbst implementieren
Wenn du einfach einen Server mit ASP.NET nimmst, dann kannst du LAPack
als nicht gemanagten Code benutzen, genau so wie jede ander DLL.
Ernst.Sauer
>
> Ich habe die NRs hier, aber in PHP sieht das schon wesentlich anders aus
> z.B. existiert keine 2D Arraystruktur unter PHP und grade Zeilen- bzw
> Spaltenoperationen muss ich schon komplett selbst implementieren
>
Ein Array braucht man nicht, denn die H�lle der Matrix kann
man in kompakter Form als Vektor abspeichern.
Damit kann auch die LU-Zerlegung durchgef�hrt werden;
anschlie�end k�nnen bei Bedarf die Spalten der Kehrmatrix ermittelt
werden. M�sste man in den NRs usw. finden.
Gru�
E.S.
Philipp Kraus
ASP gibt es aber nicht für Unix Maschinen und auf einem Webhoster kann
ich nicht einfach eine DLL (*.dll, *.dylib, *.so) nachladen.
Philipp Kraus
> Am 13.01.2011 23:51, schrieb Philipp Kraus:
>>
>> Ich habe die NRs hier, aber in PHP sieht das schon wesentlich anders aus
>> z.B. existiert keine 2D Arraystruktur unter PHP und grade Zeilen- bzw
>> Spaltenoperationen muss ich schon komplett selbst implementieren
>>
>
> Ein Array braucht man nicht, denn die Hülle der Matrix kann
> man in kompakter Form als Vektor abspeichern.
> Damit kann auch die LU-Zerlegung durchgeführt werden;
> anschließend können bei Bedarf die Spalten der Kehrmatrix ermittelt
> werden. Müsste man in den NRs usw. finden.
Naja ein Array ist ja letztendlich ein Vektor. Ich speichere intern
auch keine 2D Struktur, sondern ein 1D Struktur der Matrix.
Ich benutze unter PHP dazu ein assoziatives Array, weil ich so die
Daten als sparse-Struktur speichern, bei symmetrischen Matrizen ist das
schon eine Speicherersparnis
Problematisch ist aber, dass einfach das ganze zu langsam ist und ich
an die max. Ausführungszeit eines Scriptes stoße
(http://www.php.net/manual/de/info.configuration.php#ini.max-execution-time)
Danke
Phil
Knut
>> Wenn du einfach einen Server mit ASP.NET nimmst, dann kannst du LAPack
>> als nicht gemanagten Code benutzen, genau so wie jede andere DLL.
> ASP gibt es aber nicht für Unix Maschinen
Gibts auch, Stichwort "ASP on UNIX", z.B. Apache with FP Extensions.
> und auf einem Webhoster kann ich nicht einfach eine DLL [] nachladen
Und auch das geht, z.B. für Euro 9,95
http://www.ecs-webhosting.de/de/shared-webhosting.htm
Knut
> Problematisch ist aber, dass einfach das ganze zu langsam ist und ich
> an die max. Ausführungszeit eines Scriptes stoße
Demnach schreibst du also "nicht nur so" eine Matrixklasse sondern
hast also doch auch eine ganz praktische Aufgabenstellung. Vielleicht
beschreibst du diese für die Leute hier mal etwas konkreter, so dass
die gezielter Ideen erbrüten können. Zur max_execution_time fällt mir
spontan als "Trick" ein, dass man die Rechnung aufteilt und dann durch
zusätzliche eingebrachte Roundtrips (Click here) zusammenführt.
Knut
> Problematisch ist aber, dass einfach das ganze zu langsam ist
> und ich an die max. Ausführungszeit eines Scriptes stoße
Die Suche nach 'fast matrix inversion ' ergibt z.B. uva.
http://en.wikipedia.org/wiki/Strassen_algorithm
Demnach ist http://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm
(2008) übrigens am schnellsten.
Vielleicht interessiert dich auch die Pseudoinverse
http://www.google.de/search?q=fast+pseudoinverse
Ernst.Sauer
> On 2011-01-14 15:48:58 +0100, Ernst.Sauer said:
...
>> Ein Array braucht man nicht, denn die Hülle der Matrix kann
>> man in kompakter Form als Vektor abspeichern.
>
> Naja ein Array ist ja letztendlich ein Vektor.
Aber man braucht nur die "Hülle" der Matrix abzuspeichern.
Da die Nullen ausserhalb der Hülle sowie die symmetrischen Werte
für die Lösung nicht benötigt werden, braucht man sie auch nicht
abzuspeichern.
Am geeignetsten ist die Abspeicherung der Hülle der Spalten.
Machst Du das schon?
Knut
> Aber man braucht nur die "Hülle" der Matrix abzuspeichern.
> Da die Nullen ausserhalb der Hülle sowie die symmetrischen Werte
> für die Lösung nicht benötigt werden, braucht man sie auch nicht
> abzuspeichern.
> Am geeignetsten ist die Abspeicherung der Hülle der Spalten.
Hast du dafür bitte mal Metacode oder eine beschreibende Stelle.
Ernst.Sauer
Das findet man in diversen Büchern über die Methode der Finiten
Elemente. Aber auch in den Numerical Recipes müsste man was finden.
Schau mal auf die Seiten 683ff von
http://utopia.duth.gr/~iaitidis/Zienkiewicz%20O.C.,%20Taylor%20R.L.,%20Zhu%20J.Z.%20The%20finite%20element%20method..%20its%20basis%20and%20fundamentals%20%286ed.,%20Elsevier,%202005%29%28ISBN%200750663200%29%28802s%29_MNf_.pdf
In der älteren Auflage des Buches war auch ein Fortran Programm
abgedruckt, das sehe ich jetzt nicht mehr. Die älteren Auflagen
des Buches sollten in den Uni-Bibliotheken noch zu finden sein.
Schau mal auf die Seite
http://www.ce.berkeley.edu/projects/feap/feappv/
Vielleicht findest Du dort den Quellcode. Ich hab mir
das mal heruntergeladen, habe aber die Datei für den
Gleichungslöser noch nicht gefunden.
Eine andere Quelle wäre das Teubner-Buch
"H.R. Schwarz Methode der finiten Elemente".
Dort gibt es ein Kapitel über hüllenorientierte Rechentechniken
und Quellcode in Fortran.
Gruß
E.S.
Philipp Kraus
Da aber die Klassen innerhalb eines Plugins für ein CMS, das
ausschließlich auf PHP Basis arbeitet eingesetzt werden sollen, kann
man eben _nicht_ davon ausgehen, dass das CMS irgendwelche externen
Sachen nicht nutzen kann.
Sprich der Ansatz von Dir ist nicht möglich, außerdem ist es nicht
immer praktikabel, dass man einfach irgendetwas anderes einsetzt, nur
weil man das in den aktuellen Gegebenheiten nicht hinbekommt.
Philipp Kraus
> Philipp Kraus schrieb:
>
>> Problematisch ist aber, dass einfach das ganze zu langsam ist und ich
>> an die max. Ausf�hrungszeit eines Scriptes sto�e
>
> Demnach schreibst du also "nicht nur so" eine Matrixklasse sondern
> hast also doch auch eine ganz praktische Aufgabenstellung. Vielleicht
> beschreibst du diese f�r die Leute hier mal etwas konkreter, so dass
> die gezielter Ideen erbr�ten k�nnen. Zur max_execution_time f�llt mir
> spontan als "Trick" ein, dass man die Rechnung aufteilt und dann durch
> zus�tzliche eingebrachte Roundtrips (Click here) zusammenf�hrt.
Aber gerne doch :-P
Ich schreibe im Moment an einem Plugin f�r Wordpress, das die Artikel
des Blogs visualisieren soll. Die Artikel werden als Dissimilarity
Matrix dargestellt und nun via HITMDS
(http://dig.ipk-gatersleben.de/hitmds/hitmds.html) visualisiert. Da ich
eben f�r den Algorithmus das ganze als Matrixoperationen umsetzen will,
muss ich eben die Matrixstrukturen selbst implementieren (und ich will
nat�rlich nicht nur die Operationen implementieren die ich brauche).
Inzwischen habe ich das auch schon hinbekommen, dass es l�uft. Die
Executation Problematik umgehe ich eben dadurch, dass einfach via
"set_time_limit" einfach entsprechend umsetze. Aber das Problem ist,
dass eben PHP f�r solche Strukturen eben nicht schnell genug ist. Ich
hatte hier schon mal �berlegt ob ich meine eigene PHP Extension
schreibe, die wiederum auf die Boost und LAPack aufsetzt nur damit
bekomme ich das Problem, dass das Plugin nicht mehr dem Wordpress Codex
entspricht. D.h. da ich das Plugin auch allgm. zur Verf�gung stellen
m�chte und nur von einer existierenden Wordpress Installation und der
damit verbunden Systemanforderungen ausgehen kann, muss das ganze
ausschlie�lich unter PHP implementiert werden
Danke
Phil
Philipp Kraus
> ... zusätzliche eingebrachte Roundtrips (Click here) zusammenführt.
Der *klick* klappt leider nicht, da fehlt die URL in dem NNTP Post
Knut
>>> ASP gibt es aber nicht für Unix Maschinen
>>
>> Gibts auch, Stichwort "ASP on UNIX", z.B. Apache with FP Extensions.
>>
>>> und auf einem Webhoster kann ich nicht einfach eine DLL [] nachladen
>>
>> Und auch das geht, z.B. für Euro 9,95
>> http://www.ecs-webhosting.de/de/shared-webhosting.htm
>
> Da aber die Klassen innerhalb eines Plugins für ein CMS,
> das ausschließlich auf PHP Basis arbeitet eingesetzt werden sollen
Auch das sagstest du bisher nicht.
Und auch diese Information (der Existenz "ASP on UNIX", wie
z.B. Apache with FP Extensions) als Berichtigung deiner nicht
zutreffenden Aussage war deshalb auch für die Allgemeinheit
und nicht nur für dich. Also: keine Panik.
Philipp Kraus
Klingt sehr interessant, das werde ich mir mal anschauen
Danke
Phil
Knut
> Ich schreibe im Moment an einem Plugin für Wordpress, das die Artikel
> des Blogs visualisieren soll. Die Artikel werden als Dissimilarity
> Matrix dargestellt und nun via HITMDS
> (http://dig.ipk-gatersleben.de/hitmds/hitmds.html) visualisiert. Da ich
> eben für den Algorithmus das ganze als Matrixoperationen umsetzen will,
> muss ich eben die Matrixstrukturen selbst implementieren (und ich will
> natürlich nicht nur die Operationen implementieren die ich brauche).
Na dann...
> Inzwischen habe ich das auch schon hinbekommen, dass es läuft. Die
> Executation Problematik umgehe ich eben dadurch, dass einfach via
> "set_time_limit" einfach entsprechend umsetze. Aber das Problem ist,
> dass eben PHP für solche Strukturen eben nicht schnell genug ist.
Sicherlich sollte man dann unbedingt die assoziativen Arrays vermeiden
(wenn/da die in jeder Schleife x-fach aufwendig interpretiert werden)...
> Ich hatte hier schon mal überlegt ob ich meine eigene PHP Extension
> schreibe, die wiederum auf die Boost und LAPack aufsetzt nur damit
> bekomme ich das Problem, dass das Plugin nicht mehr dem Wordpress Codex
> entspricht. D.h. da ich das Plugin auch allgm. zur Verfügung stellen
> möchte und nur von einer existierenden Wordpress Installation und der
> damit verbunden Systemanforderungen ausgehen kann, muss das ganze
> ausschließlich unter PHP implementiert werden
Da fällt mir http://www.google.de/search?hl=de&q=fast+php+profiling ein ;)
-> http://www.ibm.com/developerworks/opensource/library/os-php-fastapps2/
Hast du dich schon für einen Algorithmus entschieden oder bleibt das
ein Running Target? Bzw. muss es dann eine Matrix Inversion sein?
Christopher Creutzig
> Ich schreibe im Moment an einem Plugin für Wordpress, das die Artikel
> des Blogs visualisieren soll. Die Artikel werden als Dissimilarity
> Matrix dargestellt und nun via HITMDS
> (http://dig.ipk-gatersleben.de/hitmds/hitmds.html) visualisiert. Da ich
> eben für den Algorithmus das ganze als Matrixoperationen umsetzen will,
> muss ich eben die Matrixstrukturen selbst implementieren (und ich will
> natürlich nicht nur die Operationen implementieren die ich brauche).
Was willst Du denn alles implementieren? Es gibt viele
Matrixoperationen die wesentlich wichtiger sind als ausgerechnet das
Invertieren, etwa SVD, LU- und QR-Zerlegung, Exponentialfunktion,
Eigenwert- und Eigenvektorberechnung usw.
Aus Sicht des Praktikers kann ich nur empfehlen: Implementier genau
das, was Du brauchst, sonst wirst Du nicht in endlicher Zeit fertig. Das
Aufwendigste scheint mir in diesem Algorithmus die Wurzelfunktion für
Matrizen zu sein; intensiv studiert habe ich ihn allerdings nicht. Eine
Matrix-Invertierung kann ich zumindest in der MATLAB-Implementation
nicht entdecken.
--
Aufhebung der Pressefreiheit und Verbot von Stammtischen
scheinen mir keine brauchbaren Alternativen zu sein ...
(Martin Bienwald)
Philipp Kraus
> Sicherlich sollte man dann unbedingt die assoziativen Arrays vermeiden
> (wenn/da die in jeder Schleife x-fach aufwendig interpretiert werden)...
Im Moment ist es eine Idee, wie ich die 2D Matrix Struktur als 1D
Struktur abbilden kann. Ich denke aber ich werde das anders indizieren.
Ich möchte eine sparse Struktur der Matrix beibehalten.
> Da fällt mir http://www.google.de/search?hl=de&q=fast+php+profiling ein ;)
>
> -> http://www.ibm.com/developerworks/opensource/library/os-php-fastapps2/
XDebug kannte ich noch nicht, das war ein guter Tipp. Auf dem
Produktivsystem ist noch ein Cache (EAccelerator), so dass ich da schon
mal etwas gewinnen kann
> Hast du dich schon für einen Algorithmus entschieden oder bleibt das
> ein Running Target? Bzw. muss es dann eine Matrix Inversion sein?
Nein, es ist kein Running Target. Ich möchte mehrere Algroithmen aus
dem maschinellen Lernen in Wordpress nutzen, wobei diese Algorithmen
meist auf Matrix Operationen bestehen, d.h. ich brauche eben eine
Matrix Klasse. Da aber eine Matrix Inversion immer "teuer" ist, war
eben genau dort mein Ansatz sie zuerst einmal zu Testzwecken zu
implementieren.
Gus Gassmann
> On 2011-01-15 21:11:52 +0100, Knut said:
>
> > Sicherlich sollte man dann unbedingt die assoziativen Arrays vermeiden
> > (wenn/da die in jeder Schleife x-fach aufwendig interpretiert werden)...
>
> Im Moment ist es eine Idee, wie ich die 2D Matrix Struktur als 1D
> Struktur abbilden kann. Ich denke aber ich werde das anders indizieren.
Dann kommt eigentlich nur das "Yale format" in Frage (http://
en.wikipedia.org/wiki/Sparse_matrix). Lapack ist open-source, also
solltest du das in PHP übersetzen können (wobei ich mir denke, dass es
hierzu wohl kaum ein Übersetzungsprogramm geben wird). Wie gross sind
eigentlich deine Matrizen, und wie dünn besetzt?
> > Da f llt mirhttp://www.google.de/search?hl=de&q=fast+php+profilingein ;)
>
> > ->http://www.ibm.com/developerworks/opensource/library/os-php-fastapps2/
>
> XDebug kannte ich noch nicht, das war ein guter Tipp. Auf dem
> Produktivsystem ist noch ein Cache (EAccelerator), so dass ich da schon
> mal etwas gewinnen kann
>
> > Hast du dich schon f r einen Algorithmus entschieden oder bleibt das
> > ein Running Target? Bzw. muss es dann eine Matrix Inversion sein?
>
> Nein, es ist kein Running Target. Ich m chte mehrere Algroithmen aus
Philipp Kraus
> On Jan 15, 6:11 pm, Philipp Kraus <philipp.kr...@flashpixx.de> wrote:
>> On 2011-01-15 21:11:52 +0100, Knut said:
>>
>>> Sicherlich sollte man dann unbedingt die assoziativen Arrays vermeiden
>>> (wenn/da die in jeder Schleife x-fach aufwendig interpretiert werden)...
>>
>> Im Moment ist es eine Idee, wie ich die 2D Matrix Struktur als 1D
>> Struktur abbilden kann. Ich denke aber ich werde das anders indizieren.
>> Ich m chte eine sparse Struktur der Matrix beibehalten.
>
> Dann kommt eigentlich nur das "Yale format" in Frage (http://
> en.wikipedia.org/wiki/Sparse_matrix). Lapack ist open-source, also
> solltest du das in PHP übersetzen können (wobei ich mir denke, dass es
> hierzu wohl kaum ein Übersetzungsprogramm geben wird). Wie gross sind
> eigentlich deine Matrizen, und wie dünn besetzt?
Die Matrizengröße wächst quadratisch mit der Datenmenge (die ist
benutzerabhängig), d.h. (Anzahl-Artikel des Blogs)^2 Die Hauptdiagonle
ist immer 0 und optional sofern es der Benutzer einstellt brauche ich
nur die obere oder untere Dreiecksmatrix. Die Elemente, die dann übrig
bleiben, können numerisch null sein, aber das habe ich noch nicht
implementiert. Im Grunde reicht mir eine Darstellung der Zahlen auf 4-6
Nachkommastellen.
Ja ich weiß, dass ich LAPack überstzen kann, aber ich muss es ja dann
als Modul laden und das ist je nach Webanbieter nicht immer möglich
bzw. muss ich das Webmodul spezifisch für die installierte PHP Version
übersetzen und das ist nicht so möglich. Da das Plugin in das allgm
Wordpress SVN rein soll, müsste ich dann auch die Modulpflege mit
machen und das ist einfach nicht möglich, da es zu viele
unterschiedliche Installationen von PHP gibt
Phil
Philipp Kraus
> On 1/15/11 8:49 PM, Philipp Kraus wrote:
>
>> Ich schreibe im Moment an einem Plugin f�r Wordpress, das die Artikel
>> des Blogs visualisieren soll. Die Artikel werden als Dissimilarity
>> Matrix dargestellt und nun via HITMDS
>> (http://dig.ipk-gatersleben.de/hitmds/hitmds.html) visualisiert. Da ich
>> eben f�r den Algorithmus das ganze als Matrixoperationen umsetzen will,
>> muss ich eben die Matrixstrukturen selbst implementieren (und ich will
>> nat�rlich nicht nur die Operationen implementieren die ich brauche).
>
> Was willst Du denn alles implementieren? Es gibt viele
> Matrixoperationen die wesentlich wichtiger sind als ausgerechnet das
> Invertieren, etwa SVD, LU- und QR-Zerlegung, Exponentialfunktion,
> Eigenwert- und Eigenvektorberechnung usw.
Ich brauche noch Eigenwerte / -vektoren, SVD, LU f�r das invertieren
und halt eben Standarddinge wie Vektor-Matrix-Multiplikation, Addition,
etc.
Ich erinnere mich gerade an meine Numerik Vorlesung, dass ich LU und
Cholesky Zerlgung auch mal selbst implementiert habe, denn f�r das
Invertieren w�rde ja LU reichen, sofern ich eben keine Sparse-Matrix
habe. Bei sparse w�rde ich ja die Cholesky Zerlegung verwenden. F�r die
Eigenwerte bzw vektoren, denke ich reicht es wenn ich nur die Vektoren
ermittle und das kann ich via Perron-Frobenius-Theorem machen. Bei der
SVD muss ich aber im Moment passen, da ich das bissher nur via LAPack &
Matlab nutze.
Gibt es ein Kriterium, wann eine Matrix als sparse gilt? Denn f�r eine
volle Matrix w�re ja die LU sinnvoller als die Cholesky. Ich benutze
intern ja eine sparse Struktur, wei� also wie viele Elemente meiner
Matrix 0 bzw nicht-null sind. Ich m�sste ja, wenn ich das Inverse bilde
eben nur intern ausw�hlen, ob LU oder Cholesky Zerlegung genutzt werden
soll.
Gus Gassmann
> On 2011-01-15 23:33:06 +0100, Gus Gassmann said:
>
> > On Jan 15, 6:11 pm, Philipp Kraus <philipp.kr...@flashpixx.de> wrote:
> >> On 2011-01-15 21:11:52 +0100, Knut said:
>
> >>> Sicherlich sollte man dann unbedingt die assoziativen Arrays vermeiden
> >>> (wenn/da die in jeder Schleife x-fach aufwendig interpretiert werden)...
>
> >> Im Moment ist es eine Idee, wie ich die 2D Matrix Struktur als 1D
> >> Struktur abbilden kann. Ich denke aber ich werde das anders indizieren.
> >> Ich m chte eine sparse Struktur der Matrix beibehalten.
>
> > Dann kommt eigentlich nur das "Yale format" in Frage (http://
> > en.wikipedia.org/wiki/Sparse_matrix). Lapack ist open-source, also
> > solltest du das in PHP übersetzen können (wobei ich mir denke, dass es
> > hierzu wohl kaum ein Übersetzungsprogramm geben wird). Wie gross sind
> > eigentlich deine Matrizen, und wie dünn besetzt?
>
> Die Matrizengröße wächst quadratisch mit der Datenmenge (die ist
> benutzerabhängig), d.h. (Anzahl-Artikel des Blogs)^2 Die Hauptdiagonle
> ist immer 0 und optional sofern es der Benutzer einstellt brauche ich
> nur die obere oder untere Dreiecksmatrix. Die Elemente, die dann übrig
> bleiben, können numerisch null sein, aber das habe ich noch nicht
> implementiert. Im Grunde reicht mir eine Darstellung der Zahlen auf 4-6
> Nachkommastellen.
OK. Deine Matrizen sind quadratisch und symmetrisch. Dann kommt eine
Cholesky-Zerlegung in Frage. Das kannst du auch numerisch stabil
implementieren. Aber deinen letzten Satz verstehe ich überhaupt nicht.
Wenn du numerische Probleme erwartest, kannst du dich nicht mit 32
Bits zufrieden geben. Wenn die Matrizenelemente nicht ganzzahlig sind,
musst du sie schon mit soviel Präzision darstellen, wie möglich.
Gus Gassmann
> Gibt es ein Kriterium, wann eine Matrix als sparse gilt? Denn f r eine
> volle Matrix w re ja die LU sinnvoller als die Cholesky. Ich benutze
> intern ja eine sparse Struktur, wei also wie viele Elemente meiner
> Matrix 0 bzw nicht-null sind. Ich m sste ja, wenn ich das Inverse bilde
> eben nur intern ausw hlen, ob LU oder Cholesky Zerlegung genutzt werden
> soll.
Du wirfst hier einiges durcheinander. Cholesky ist im Grunde eine LU-
Zerlegung für symmetrische Matrizen. Beides kannst du für volle und
weniger volle Matrizen anwenden und implementieren, wenn du die
geeignete Datenstruktur wählst. Wann eine Matrix als voll zu gelten
hat, ist deshalb ziemlich einfach: Wenn die volle Form weniger
Speicherplatz wegnimmt als das Yale Format, was bei ungefähr einer
halb besetzten Matrix eintreten dürfte.
Ernst.Sauer
...
...
> Die Matrizengröße wächst quadratisch mit der Datenmenge (die ist
> benutzerabhängig), d.h. (Anzahl-Artikel des Blogs)^2
> Die Hauptdiagonle ist immer 0
???
Christopher Creutzig
> Gibt es ein Kriterium, wann eine Matrix als sparse gilt?
Als Eigenschaft von Matrizen, im Gegensatz zur Klassifikation von
Speicherformaten, ist �sparse� keine bin�re Eigenschaft, sondern man
kann allenfalls angeben, �wie sparse� (genauer: �how sparse� oder �wie
d�nn besetzt�) eine Matrix ist. Ob bei Deiner konkreten Implementation
bei einer Matrixgr��e von 500x500 bei einem Besetzheitsgrad von 39.5%
der eine oder andere Algorithmus besser funktioniert, ist eher eine
experimentell zu kl�rende Frage � und kann nur einen Mittelwert liefern,
weil das Verhalten noch von vielen weiteren Details abh�ngt, etwa der
Form des Besetzungsmusters und nat�rlich auch den konkret eingesetzten
Werten. Aber mit genug Messdaten kann man eine vern�nftige Heuristik f�r
die Auswahl implementieren.
--
Geht die Sonne auf im Westen, musst du deinen Kompass testen.