Ordnen Sie eine gewöhnliche Matrix neu an, um die diagonale Form zu blockieren

8

Gibt es einen Algorithmus zum Umordnen einer Matrix in blockdiagonale Form, da die Matrix blockdiagonaler Natur ist, aber mit einer unklugen Wahl der Basis randomisiert wird?

Gibt es dafür insbesondere Python-Module?

matrix python Maschine
quelle
2
Möchten Sie die Matrix durch eine Permutation oder einen Basiswechsel "neu anordnen"?
Christian Clason
1
Ich wollte ursprünglich die Basis permutieren, die ich für einfach zu halten halte. Der Fall einer Änderung der Basis kann durch ein physikalisches Argument erfolgen, wenn die Matrix ein Hamilton-Operator ist, aber für eine allgemeine Matrix wäre dies ziemlich schwierig.
Maschine
Sie könnten interessiert sein an Wie kann ich Matrizen so umstrukturieren, dass Elemente ungleich Null nahe der Diagonale liegen?
Martin Thoma

Antworten:

7

Ist die Matrix dünn oder dicht? Ist es symmetrisch?

n×nAijAij≠0

Die Tatsache, dass Ihre Matrix eine Blockdiagonale (bis zu einer Neuordnung) aufweist, bedeutet, dass das Diagramm nicht verbunden ist. Wenn Sie herausfinden, welche Scheitelpunkte in einem Block zusammen sein sollten, müssen Sie die verbundenen Komponenten des Diagramms ermitteln. Sie können dies mit einer Breitensuche tun . Da die umgekehrte Cuthill-McKee-Reihenfolge einer Matrix im Wesentlichen eine Breitensuche ist, können Sie wahrscheinlich den Python-Code einer anderen Person für die RCM-Reihenfolge finden und direkt verwenden oder für Ihre Zwecke ändern.

Daniel Shapero
quelle
Vielen Dank! Angenommen, die Matrix ist dünn und symmetrisch (Einsiedler).
Maschine
3

Jede Matrix ist in einer klugen Wahl der Basis blockdiagonal - dies wird als Jordan-Normalform bezeichnet , und die Basis besteht aus ihren verallgemeinerten Eigenvektoren. Wenn die Matrix symmetrisch ist, besteht diese Basis aus Eigenvektoren, und Sie können sie beispielsweise mit dem QR-Algorithmus berechnen . SciPy bietet das Modul linalg.qrzur Berechnung der erforderlichen QR-Zerlegungen. Andernfalls können Sie die Singularwertzerlegung verwenden , die mit berechnet werden kann linalg.svd.

Christian Clason
quelle
2
Die Verwendung der Jordan-Normalform ist eine wirklich schlechte Idee, da sie numerisch instabil ist . Eine bessere Wahl wäre eine numerisch stabile Schur-Zerlegung auf Kosten der Neuanordnung Ihrer Matrix in eine Matrix mit einem oberen Dreieck.
Geoff Oxberry
Natürlich, und ich habe nicht vorgeschlagen, es zu berechnen, außer für symmetrische Matrizen, bei denen es mit der Schur-Zerlegung zusammenfällt (und es kann stabil mit dem QR-Algorithmus berechnet werden). Für allgemeine unsymmetrische Matrizen kenne ich keinen besseren Ansatz zur Diagonalisierung einer Matrix als die SVD.
Christian Clason
2
Und das ist ein guter Punkt. Ich würde nicht sagen, dass SVD eine Matrix "diagonalisiert". Während es eine Zerlegung ergibt, die eine diagonale Matrix enthält, wird die Diagonalisierung traditionell verwendet, um sich auf eine Ähnlichkeitstransformation (oder eine Zerlegung basierend auf einer solchen Transformation / Basisänderung) zu beziehen, die zu einer diagonalen (oder blockdiagonalen) Matrix führt. SVD ist keine Ähnlichkeitstransformation, obwohl es eine außerordentlich nützliche Zerlegung ist.
Geoff Oxberry
Punkt genommen (und in diesem Sinne ist nicht jede Matrix diagonalisierbar). Ich möchte auch darauf hinweisen, dass die Diagonalisierung durch eine nicht einheitliche Ähnlichkeitstransformation sehr instabil sein kann.
Christian Clason