Was ist die entsprechende LAPACK-Funktion hinter Matlab [Q, R, E] = qr (A)?

Ich versuche derzeit, eine gute Rangschätzung für eine Matrix billig zu berechnen . Daher berechne ich eine columnt schwenkbare QR-Zerlegung mit $A$

[Q,R,E]=qr(A)

in Matlab. Ich schätze den Rang von mit $A$

tol = size(A,n)*eps*norm(A,'fro'); 
r = sum(abs(diag(R))>tol)

Dies funktioniert gut und ein Plot über alle diagonalen Einträge von R sieht aus wie: plot (sort (abs (diag (R)), 1, 'desc'), 'r *')

Wenn der gesamte Algorithmus auf C / Fortran I portiert wird, ersetze ich [Q, R, E] = qr (A) mit DGEQP3 von LAPACK, das auch eine Spalte berechnet, die die QR-Zerlegung schwenkt. Aber wenn ich die gleiche Schätzung für den Rang verwende, verstehe ich meistens etwas falsch. Das gleiche Grundstück für die aus DGEQP3 produziert aussieht $R$

Die Eingabematrix ist für beide Experimente genau gleich.

Meine Frage ist nun, auf welche LAPACK-Funktion sich die spaltenschwenkende QR-Zerlegung von Matlab stützt.

Danke für jede Hilfe, Grisu

Bearbeiten: DGEQPF liefert das gleiche falsche Ergebnis.

Edit2:

Die Eingabematrix ist dicht und wird als $A$ $E+sign(E,F)$
$A$
$R$
Ich habe LAPACK 3.4.0 mit OpenBlas / GotoBLAS (64 Bit) verwendet.
Matlab 7, 2007b, 2010b Linux 32bit

Edit3: - Mit GDB habe ich herausgefunden, dass Matlab 2010b DGEQP3: # 3 0xaa46ce2f in dgeqp3_ () von /usr/ubuntu10.04/matlabr2010b/bin/glnx86/../../bin/glnx86/../ aufruft. ./bin/glnx86/mllapack.so Warum erhalte ich mit LAPACK das falsche Ergebnis (3.4.0 einschließlich der in Working Note 176 genannten Korrekturen)?

matlab lapack MK aka Grisu
quelle

Können Sie dasselbe Verhalten mit einer kleineren Matrix provozieren, die Sie möglicherweise hier teilen können?

GertVdE

A

$A$

A

$A$

Grisu - Ich würde gerne Ihre Matrix betrachten. Der Link www-e.uni-magdeburg.de/makoehle/A.mtx.gz ist jedoch nicht mehr aktiv (jedenfalls zum gegenwärtigen Zeitpunkt). Haben Sie einen aktuellen Link zur Matrix? Vielen Dank, Les Foster

@LeslieFoster - Willkommen bei scicomp!

Aron Ahmadia

Antworten:

Hier gibt es zwei Probleme:

$A$
Haben Sie den gleichen Software-Stack wie die internen Bibliotheken von MATLAB?

Dicht oder spärlich?

$A$ DGEQP3[Q,R,E] = qr(A) $A$

Haben Sie den gleichen Software-Stack wie die internen Bibliotheken von MATLAB?

Wahrscheinlich nicht, was möglicherweise ein Grund dafür ist, dass Sie unterschiedliche Ergebnisse erzielen.

Ich bin auf dieses Problem gestoßen, als ich eine von mir geschriebene Bibliothek mit QR-Faktorisierungen getestet habe. Ich habe MATLAB als Prototyp für meine Arbeit verwendet und andere Ergebnisse erzielt als mit LAPACK oder NumPy. Soweit ich das beurteilen kann, verwendet MATLAB eine Version von LAPACK nicht früher als Version 3.1.1 und Intels MKL BLAS-Bibliothek (für Windows, Intel Mac und Linux), Version 9.1, da MathWorks diese Informationen nicht leicht zu finden macht oder höher (siehe hier ). Ich konnte nichts über die Version von SuiteSparse MATLAB finden. Wenn Sie online stöbern oder die Bibliotheksdateien für Ihr System anzeigen, können Sie möglicherweise zusätzliche Informationen abrufen. Sie können versuchen, die Bibliotheken zu ändern, mit denen MATLAB verknüpft ist, um über Softwarepakete hinweg mit denselben Bibliotheken vergleichen zu können. Eric Chu bietet eine schöne ZusammenfassungDas zeigt zumindest, wie Sie die BLAS-Bibliothek von MATLAB durch Ihre eigene ersetzen können (dies geschieht natürlich auf eigenes Risiko). Er schlägt vor, dass Sie dasselbe auch mit LAPACK tun können. Möglicherweise kann sogar die von MATLAB verwendete Version von SuiteSparse durch Ihre eigene Version ersetzt werden.

$A = QR$ $Q$ $R$

Am Ende habe ich NumPy verwendet, um meine Ergebnisse für die QR-Faktorisierung zu prototypisieren, da die System-BLAS- und LAPACK-Bibliotheken verwendet werden. NumPy und SciPy sind kein Ersatz für MATLAB, da den beiden Bibliotheken zusammen einige Funktionen von MATLAB fehlen. Für diese spezielle lineare Algebra-Aufgabe sollte Python + NumPy + SciPy + Matplotlib jedoch gut funktionieren.

Geoff Oxberry
quelle

Den gleichen Software-Stack wie Matlab zu bekommen, ist meiner Meinung nach unmöglich. Die Verwendung einer anderen Umgebung für das Prototyping ist ebenfalls nicht erwünscht. Das Problem ist, dass der Code in Matlab korrekt funktioniert, aber nicht in C.

MK aka Grisu

@Grisu: Ich denke, es wäre sehr schwierig, denselben Software-Stack zu bekommen, ohne zu versuchen, eine Verknüpfung in ihren Bibliotheken herzustellen. Was mich verwirrt, ist, woher Sie wissen, dass das Ergebnis in MATLAB korrekt und das Ergebnis in C falsch ist. Ist dies eine Art Testmatrix mit bekannten Eigenschaften? Genauer gesagt, AronAhmadia hat recht; Abgesehen von der Replikation der Architektur und des Software-Stacks können Sie nicht erwarten, mit einem instabilen Algorithmus dieselben Ergebnisse zu erzielen. Vor zwei Jahren wurde mir in den MATLAB-Foren im Grunde dasselbe gesagt.

Geoff Oxberry

Meiner Meinung nach ist der QR nicht instabil. Ich kann nicht direkt überprüfen, welche QR-Zerlegung richtig ist, aber anhand des Ranges und der Q-Matrix berechne ich einen Projektor und dort kann ich leicht überprüfen, ob gute oder schlechte Ergebnisse erzielt werden und die von Matlab gut sind. Aber ich versuche, gegen die Matlab-Bibliotheken zu verlinken.

MK aka Grisu

@Grisu: Es gibt einen deutlichen Unterschied zwischen guten und korrekten Ergebnissen. Ich habe kürzlich eine Berechnung falsch implementiert, die meine Ergebnisse wunderbar aussehen ließ. Trotzdem war die Berechnung falsch und die korrekte Berechnung ließ meine Ergebnisse weniger beeindruckend aussehen (zeigt aber zum Glück, dass meine Ergebnisse korrekt sind). Versuchen Sie, einen orthogonalen Projektor oder einen schrägen Projektor zu berechnen? (Ich frage, weil wesentliche Teile meiner Arbeit auf Schrägprojektoren sind.)

Geoff Oxberry

@GeoffOxberry: fwiw, auf meiner Version von MATLAB kann ich anrufen internal.matlab.language.versionPlugins.blasund internal.matlab.language.versionPlugins.lapackBLAS- und LAPACK-Versionen erhalten

Amro

Siehe Leslie Fosters Seite über aufschlussreiche Software . Siehe auch diese LAPACK-Arbeitsnotiz zur Analyse von Fehlern bei der Aufdeckung von QRxGEQP3 .

Sie sollten herausfinden können, welche Routinen MATLAB verwendet, indem Sie Haltepunkte in einem Debugger festlegen und den Stapel untersuchen. Zuletzt habe ich vor einigen Jahren zugegeben, dass MATLAB gemeinsam genutzte Bibliotheken verwendet hat. In diesem Fall können die Symbolnamen nicht entfernt werden, sodass Sie die Funktionsnamen auf dem Aufrufstapel sehen (aber keine Argumente, da die Debugging-Informationen definitiv nicht gespeichert werden).

Jed Brown
quelle

Die Seite über rangaufschlussreiche Software hat nicht geholfen. Das dort beschriebene RRQR-Verfahren war das erste, was ich in meiner Idee verwendete, aber es liefert noch schlechtere Ergebnisse als die Idee des Säulenschwenkens.

MK aka Grisu

@Grisu - Es hätte dir helfen sollen. Der xGEQP3Algorithmus ist nicht ganz sicher, um den Rang zu ermitteln. Wenn Sie sicherstellen möchten, dass Sie das richtige Ergebnis erzielen, sollten Sie die SVD oder einen sichereren QR wie xGEQPXoder verwenden xGEQPY. Sie können nicht erwarten, dass ein instabiler Algorithmus auf verschiedenen Architekturen oder in verschiedenen Implementierungen dasselbe Ergebnis zurückgibt (MATLAB verwendet wahrscheinlich ein älteres LAPACK).

Aron Ahmadia

Ich weiß, dass der GEQP3 keinen Rang enthüllt, aber korrektere Ergebnisse liefert als die RRQR-Subroutinen. Die Verwendung einer SVD ist in meinem äußeren Algorithmus zu teuer. Ich werde auch mit einem der Autoren von LAWN-176 sprechen und er glaubt, dass dieser Fehler nicht durch den Fehler abgedeckt ist. Ich habe auch DGEQPF / DGEQP3 von LAPACK 3.0.0 mit den gleichen Ergebnissen ausprobiert.

MK aka Grisu