Matrix-Neuordnung zur Blockdiagonalform

Question

Geben Sie eine dünn besetzte Matrix, wie ordnen Sie die Zeilen und Spalten so an, dass sie in Blockdiagonalform über Zeilen- und Spaltenpermutation ist?

Zeilen- und Spaltenpermutation sind nicht notwendigerweise wie umgekehrte Cuthill-McKee-Reihenfolge gekoppelt: http://www.mathworks.com/help/matlab/ref/symrcm.html?refresh=true Kurz gesagt, Sie können jede Zeilen- oder Spaltenpermutation unabhängig ausführen.

Das Gesamtziel besteht darin, alle Nicht-Null-Elemente in Richtung Diagonale zu gruppieren.

Answer 1

Nur eine Idee, aber wenn Sie eine neue Matrix Ab von der ursprünglichen Block-Matrix A, die die Block-Sparsity-Struktur von A enthält. Z.B .:

A = [B 0 0; 0 0 C; 0 D 0]; % with matrices 0 (zero elements), B,C and D 

Ab = [1 0 0; 0 0 2; 0 3 0]; % with identifiers 1, 2 and 3 (1-->B, 2-->C, 3-->D) 

Ab Dann ist eine einfache Sparse-Matrix (Größe 3x3 in dem Beispiel). Sie können dann die umgekehrte Cuthill-McKee-Reihenfolge verwenden, um die gewünschten Permutationen zu erhalten, und diese Permutationen auf Ab anwenden.

p = symrcm(Ab); 
Abperm = Ab(p,p); 

dann die Bezeichner verwenden, um die bestellten Blockmatrix Aperm von Abperm zu erstellen, und Sie werden das gewünschte Ergebnis haben, glaube ich.

Sie müssen die Identifier den einzelnen Blöcken zuweisen, aber dies sollte möglich sein.

Answer 2

Hier ist ein Ansatz.

Zuerst erstellen Sie ein Diagramm, dessen Scheitelpunkte Zeilen und Spalten sind. Jeder Wert ungleich Null ist eine Kante zwischen dieser Zeile und dieser Spalte.

Sie können dann einen standardmäßigen graphentheoretischen Algorithmus verwenden, um die verbundenen Komponenten dieses Graphen zu erkennen. Die einzelnen Elemente repräsentieren alle null Zeilen und Spalten. Nummeriere die anderen. Diese Komponenten können ungleiche Zeilen und Spalten haben. Sie können einige Nullzeilen und Spalten auf sie verteilen, um sie quadratisch zu machen.

Ihre quadratischen Komponenten werden Ihre Blöcke sein, und aus der Nummerierung dieser Komponenten wissen Sie, in welcher Reihenfolge sie eingefügt werden sollen. Jetzt ordnen Sie einfach Zeilen und Spalten um diese Struktur zu erreichen und, voila! (Die verbleibenden Nullzeilen/Spalten ergeben eine Reihe von 0 Blöcken unten rechts auf der Diagonalen.)