Testen, ob zwei 12x12-Matrizen dieselbe Determinante haben

Ich bekomme eine Matrix , die symmetrisch, invertierbar, positiv definitiv und dicht ist. Ich muss testen, ob wobei die All-One-Matrix ist. $12 \times 12$ $Q$

det (Q) = det (12 I - Q - J) (1)

$\det(Q) = \det(12I-Q-J) \; \; (1)$

J

$J$

Ich mache das gerade mit der Gürteltierbibliothek, aber es stellt sich als zu langsam heraus. Die Sache ist, dass ich dies für eine Billion Matrizen tun muss und es stellt sich heraus, dass die Berechnung der beiden Determinanten der Engpass meines Programms ist. Daher habe ich zwei Fragen

Gibt es einen Trick, mit dem ich die Determinante schneller berechnen könnte, da ich ihre Größe kenne? Ist vielleicht eine unordentliche Erweiterung für $12 \times12$ Matrizen, die in diesem Fall funktionieren könnte?
Gibt es eine andere effiziente Möglichkeit, die Gleichheit zu testen? $(1)$

Bearbeiten. Um die Kommentare zu beantworten. Ich muss alle verbundenen nicht selbstkomplementären Graphen $G$ der Ordnung $13$ so berechnen, dass $G$ und $\overline{G}$ die gleiche Anzahl von Spannbäumen haben. Die Motivation dafür finden Sie in diesem Mathoverflow- Beitrag. Die Maschine wird parallel auf einer 8-Kern-Maschine mit 3,4 GHh ausgeführt.

Bearbeiten. Ich konnte die erwartete Laufzeit um 50% reduzieren, indem ich ein C-Programm zur spezifischen Berechnung der Determinante einer $12 \times 12$ Matrix erstellte. Vorschläge sind weiterhin willkommen.

linear-algebra matrix c++ graph-theory c Jernej
quelle

Wie langsam ist zu langsam? Wie lange dauert es auf welcher Hardware? Sind die Billionen dieser unabhängig, so dass Sie viele dieser Determinanten parallel berechnen können? Wenn ja, auf welcher Maschine können Sie laufen? Was hat zu diesem Problem geführt? Sind Sie sicher, dass Sie die Determinanten berechnen müssen?

Q

$Q$

Bill Barth

Wie oft (für welchen Teil der Fälle) sind die Determinanten gleich / verschieden? Wenn sie die meiste Zeit unterschiedlich sind, gibt es möglicherweise einen günstigeren Test, um festzustellen, ob sie unterschiedlich sind, und Sie würden überprüfen, ob sie nur dann gleich sind, wenn der erste Test fehlschlägt. Umgekehrt, wenn sie die meiste Zeit gleich sind.

Wolfgang Bangerth

Wie bereits gefragt: Können Sie uns etwas näher erläutern, woher stammt? Vielleicht gibt es einen besseren Ansatz als die blinde Berechnung von Determinanten.

Q

$\mathbf Q$

Die Vorstellung, dass diese Bedingung "für eine Billion Matrizen" getestet werden muss, legt nahe, dass 1) vornherein eine spezielle Struktur aufweist (ansonsten ist die Erwartung, dass die Bedingung zufällig gilt, gering ist) und 2) dass ein besserer Ansatz vorliegt könnte darin bestehen, alle Matrizen mit dieser Eigenschaft zu charakterisieren (mit einer effizient überprüfbaren Formulierung).

Q

$Q$

Q

$Q$

Hardmath

@hardmath Ja, ist eine ganzzahlige Matrix mit diagonalen Einträgen von bis und als nicht diagonale Elemente

Q

$Q$

1

$1$

12

$12$

- 1

$-1$

Jernej

Antworten:

Da Sie bereits C ++ verwenden und Ihre Matrizen symmetrisch positiv definit sind, würde ich eine nicht drehbare Faktorisierung von und auch von . Hier gehe ich davon aus, dass auch positiv definit ist, andernfalls muss das Gründen der numerischen Stabilität geschwenkt werden (es ist auch möglich, dass das Schwenken nicht erforderlich ist, obwohl es nicht positiv eindeutig ist, aber Sie müssen es versuchen). $LDL^T$ $Q$ $12I-Q-J$ $12I-Q-J$ $LDL^T$

Dies ist schneller als eine LU-Faktorisierung und auch schneller als Cholesky, da Quadratwurzeln vermieden werden. Die Determinante ist einfach das Produkt der Elemente der diagonalen Matrix. Der Code ein LDL - Faktorisierung durchzuführen ist so einfach , dass man es in weniger als 50 Zeilen C schreiben können Wikipedia - Seite auf den Algorithmus beschreibt, und ich habe einige einfache Templat Code Cholesky zu tun hier . Sie können dies erheblich vereinfachen und ändern, um die Quadratwurzel zur Implementierung der Faktorisierung zu vermeiden . $D$ $LDL^T$

Da Sie auch das Speicherformat steuern können, können Sie die Routine weiter optimieren, um nur die Hälfte der Matrix zu speichern und in ein lineares Array zu packen, um die Speicherlokalität zu maximieren. Ich würde auch einfache benutzerdefinierte Punktprodukt- und Rang-1-Aktualisierungsroutinen schreiben, da die Problemgrößen so klein sind, dass Sie den Compiler die Routinen einbinden lassen sollten, um den Anrufaufwand zu verringern. Da es sich um eine Schleife mit fester Größe handelt, sollte der Compiler in der Lage sein, Dinge bei Bedarf automatisch ein- und auszurollen.

Ich möchte vermeiden , zu spielen Tricks versuchen , sich die Tatsache zunutze zu tragen , dass enthält innerhalb des Ausdrucks. Es ist wahrscheinlich, dass diese Tricks bei solch kleinen Problemgrößen langsamer sind als nur zwei separate Determinantenberechnungen durchzuführen. Die einzige Möglichkeit, diese Behauptungen zu überprüfen, besteht natürlich darin, es zu versuchen. $12I-Q-J$ $Q$

Victor Liu
quelle

Ich stimme der Empfehlung zu, , auch bekannt als root-free Cholesky, zu implementieren , da Armadillo keine Möglichkeit zu haben scheint, die positive Bestimmtheit / diagonale Dominanz auszunutzen.

L D L^{T}

$LDL^T$

Hardmath

Ohne einige Informationen über die Konstruktion dieser positiv definierten reellen symmetrischen Matrizen sind die zu machenden Vorschläge notwendigerweise ziemlich begrenzt. $12\times 12$

Ich habe das Armadillo-Paket von Sourceforge heruntergeladen und mir die Dokumentation angesehen. Versuchen Sie, die Leistung der getrennten Berechnung von und zu verbessern , wobei die Rang-1-Matrix aller ist, indem Sie z . In der Dokumentation wird darauf hingewiesen, dass dies die Standardeinstellung für Matrizen bis zu einer Größe von ist. Daher gehe ich davon aus, dass die Option eine Standardeinstellung für den Fall ist. $\det(Q)$ $\det(12I - Q - J)$ $J$ det(Q,slow=false) $4\times 4$ slow=true $12\times 12$

Was slow=true vermutlich tut, ist ein teilweises oder vollständiges Schwenken, um eine Reihenebenenform zu erhalten, aus der die Determinante leicht gefunden werden kann. Sie wissen jedoch im Voraus, dass die Matrix eindeutig positiv ist, sodass ein Schwenken für die Stabilität nicht erforderlich ist (zumindest vermutlich für den Großteil Ihrer Berechnungen. Es ist unklar, ob das Armadillo-Paket eine Ausnahme auslöst, wenn die Drehpunkte übermäßig klein werden, dies sollte jedoch eine sein Funktion eines vernünftigen numerischen linearen Algebra-Pakets. BEARBEITEN: Ich habe den Armadillo-Code gefunden, der in der Header-Datei implementiert ist , wobei C ++ - Vorlagen für wesentliche Funktionen verwendet wurden. Die Einstellung scheint keinen Einfluss darauf zu haben, wie ein $Q$ detinclude\armadillo_bits\auxlib_meat.hppslow=false $12\times 12$ Die Determinante wird durchgeführt, weil die Berechnung zu diesem Zeitpunkt an LAPACK (oder ATLAS) "über eine Mauer geworfen" wird, ohne dass darauf hingewiesen wird, dass kein Schwenken erforderlich ist. siehe det_lapackund seine Aufrufe in dieser Datei.

Der andere Punkt wäre, der Empfehlung zu folgen, das Armadillo-Paket zu erstellen, das mit Hochgeschwindigkeitsersatz für BLAS und LAPACK verknüpft ist, wenn Sie diese tatsächlich verwenden. siehe Kap. 5 der Armadillo README.TXT-Datei für Details. [Die Verwendung einer dedizierten 64-Bit-Version von BLAS oder LAPACK wird auch für die Geschwindigkeit auf aktuellen 64-Bit-Computern empfohlen.]

Die Zeilenreduktion auf die Staffelform ist im Wesentlichen eine Gaußsche Eliminierung und hat eine arithmetische Komplexität . Für beide Matrizen beträgt dies dann das Doppelte dieser Arbeit oder . Diese Operationen mögen zwar der "Engpass" in Ihrer Verarbeitung sein, aber es gibt wenig Hoffnung, dass ohne eine spezielle Struktur in (oder einige bekannte Beziehungen zwischen den Billionen Testfällen, die eine Amortisation ermöglichen) die Arbeit auf reduziert werden könnte . $\frac{2}{3} n^3 + O(n^2)$ $\frac{4}{3} n^3 + O(n^2)$ $Q$ $O(n^2)$

Zum Vergleich beinhaltet die Expansion einer allgemeinen Matrix durch CofaktorenMultiplikationsoperationen (und ungefähr ebenso viele Additionen / Subtraktionen), so dass für der Vergleich ( vs. ) eindeutig die Eliminierung gegenüber Cofaktoren begünstigt. $n\times n$ $n!$ $n=12$ $12! = 479001600$ $\frac{2}{3} n^3 = 1152$

Ein anderer Ansatz, der Arbeit erfordert, wäre die Reduzierung von auf die tridiagonale Form mit Householder-Transformationen, wodurch auch in die tridiagonale Form gebracht wird. Das Berechnen von und kann danach in Operationen durchgeführt werden. [Der Effekt der Rang-1-Aktualisierung in der zweiten Determinante kann als ausgedrückt werden, der durch Lösen eines tridiagonalen Systems gegeben ist.] $\frac{4}{3} n^3 + O(n^2)$ $Q$ $12I - Q$ $\det(Q)$ $\det(12I - Q - J)$ $O(n)$ $-J$

Die Implementierung einer solchen unabhängigen Berechnung kann sich lohnen, um die Ergebnisse erfolgreicher (oder fehlgeschlagener) Aufrufe von Armadillos detFunktion zu überprüfen .

Sonderfall: Nehmen wir an, dass wobei wie zuvor die (Rang 1) Matrix aller ist und ist nicht singuläre (positive) diagonale Matrix. In der Tat wären dies für die vorgeschlagene Anwendung in der Graphentheorie ganzzahlige Matrizen. Dann lautet eine explizite Formel für : $Q = D - J$ $J$ $D=\text{diag}(d_1,\ldots,d_n)$ $\det(Q)$

det (Q) = (\prod_{i = 1}^{n} d_{i}) (1 - \sum_{i = 1}^{n} d_{i}^{- 1})

$\det(Q) = \left(\prod_{i=1}^n d_i \right)\left(1 - \sum_{i=1}^n d_i^{-1} \right)$

Eine Skizze seines Beweises bietet die Möglichkeit, eine breitere Anwendbarkeit zu veranschaulichen, dh wenn eine bekannte Determinante hat und das System schnell gelöst ist. Beginnen Sie mit dem Ausklammern: $D$ $Dv = (1\ldots 1)^T$

det (D - J) = det (D) \cdot det (I - D^{- 1} J)

$\det(D - J) = \det(D) \cdot \det(I - D^{-1}J)$

Jetzt ist wieder Rang 1, nämlich . Beachten Sie, dass die zweite Determinante einfach ist: $D^{-1}J$ $(d_1^{-1}\ldots d_n^{-1})^T(1\ldots 1)$

f (1) = det (I - D^{- 1} J)

$f(1) = \det(I- D^{-1}J)$

wobei das charakteristische Polynom von . Als Rang-1-Matrix muss (mindestens) Faktoren von , um seinen Nullraum zu berücksichtigen. Der "fehlende" Eigenwert ist , wie aus der Berechnung ersichtlich ist: $f(x)$ $D^{-1}J$ $f(x)$ $n-1$ $x$ $\sum d_i^{-1}$

D^{- 1} J (d_{1}^{- 1} \dots d_{n}^{- 1})^{T} = (\sum d_{i}^{- 1}) (d_{1}^{- 1} \dots d_{n}^{- 1})^{T}

$D^{-1}J\; (d_1^{-1}\ldots d_n^{-1})^T = \left(\sum d_i^{-1} \right) (d_1^{-1}\ldots d_n^{-1})^T$

Daraus folgt, dass das charakteristische Polynom und wie oben für , . $f(x) = x^{n-1} (x - \sum d_i^{-1})$ $f(1)$ $\det(I - D^{-1}J)$ $1 - \sum d_i^{-1}$

Beachten Sie auch, dass wenn , dann , eine diagonale Matrix, deren Determinante einfach das Produkt ihrer diagonalen Einträge ist. $Q = D-J$ $12I - Q - J = 12I - D + J - J = 12I - D$

Hardmath
quelle

Hm .. ist in der Tat wobei die Adjazenzmatrix von daher denke ich, dass dieses Ergebnis möglicherweise nicht korrekt ist. Insbesondere würde dies bedeuten, dass die Anzahl der Spannbäume eines Graphen durch seine Gradfolge bestimmt wird, die nicht gilt.

Q

$Q$

D - A

$D-A$

A

$A$

G

$G$

G

$G$

Jernej

Die nicht diagonalen Einträge von enthalten dann im Allgemeinen 0 sowie -1. Die von Victor vorgeschlagene Zerlegung nutzt die Symmetrie und reduziert den führenden Term in der Operationsanzahl von auf . Es gibt einen exakten ganzzahligen Ansatz, der jedoch für Ihre bescheidene Größenmatrix und Einträge wahrscheinlich nicht benötigt wird. Wenn ich die Konstruktion verstehe, ist aus demselben Grund wie eindeutig positiv .

Q

$Q$

L D L^{T}

$LDL^T$

\frac{2}{3} n^{3}

$\frac{2}{3}n^3$

\frac{1}{3} n^{3}

$\frac{1}{3}n^3$

12 I - Q - J

$12I-Q-J$

Q

$Q$

Hardmath

@Jernej: Wenn Sie glauben, dass etwas, das ich angegeben habe, nicht korrekt ist, habe ich basierend auf dieser Frage einen Chatraum erstellt, in dem die Diskussion ohne unnötige Kommentare hier geführt werden kann.

Hardmath

Wenn Sie eine strukturierte Methode zur Aufzählung der Diagramme haben, für die Sie die Determinanten berechnen möchten, können Sie möglicherweise Aktualisierungen mit niedrigem Rang finden, die Sie von einem Diagramm zum anderen übertragen.

Wenn ja, können Sie das Matrix-Determinanten-Lemma verwenden , um die Determinante des nachfolgenden zu zählenden Graphen unter Verwendung Ihrer Kenntnis der Determinante des aktuellen Graphen kostengünstig zu berechnen.

Das heißt, für eine Matrix und Vektoren : Dies kann verallgemeinert werden, wenn U und V sind Matrizen und ist : $A$ $u,v$

det (A + u v^{T}) = (1 + v^{T} A^{- 1} u) det (A)

$\det(A+uv^T)=(1+v^T A^{-1} u)\det(A)$

n \times m

$n \times m$

A

$A$

n \times n

$n \times n$

det (A + U V^{T}) = det (I_{m} + V^{T} A^{- 1} U) det (A)

$\det(A+UV^T)=\det(I_m + V^TA^{-1}U)\det(A)$

Um die Inverse effizient zu berechnen, können Sie die Sherman-Morrison-Formel verwenden , um die Inverse der nachfolgenden Matrix aus der aktuellen zu erhalten:

(A + u v^{T})^{- 1} = A^{- 1} - \frac{A^{- 1} u v^{T} A^{- 1}}{1 + v^{T} A^{- 1} u}

$(A+uv^T)^{-1}=A^{-1}-\frac{A^{-1} uv^T A^{-1}}{1+v^T A^{-1} u}$

Richard
quelle