Reorganizar uma matriz comum para bloquear a forma diagonal

Existe um algoritmo para reorganizar uma matriz na forma diagonal de bloco, dado que a matriz é de natureza diagonal de bloco, mas randomizada com uma escolha imprudente de base?

Em particular, existem módulos python para isso?

matrix python Máquina
fonte

Deseja "reorganizar" a matriz por uma permutação ou por uma mudança de base?

Christian Clason

Originalmente, pretendia permutar a base que acho fácil de executar. O caso da mudança de base pode ser feito com base em algum argumento físico se a matriz for um hamiltoniano, mas para alguma matriz geral, seria bastante difícil.

Machine

Você pode estar interessado em Como posso reestruturar matrizes para ter elementos diferentes de zero perto da diagonal?

Martin Thoma 31/03

Respostas:

A matriz é esparsa ou densa? Simétrico?

$n\times n$ $A$ $i$ $j$ $A_{ij} \neq 0$

O fato de sua matriz ter diagonal de bloco (até uma reordenação) significa que o gráfico não está conectado e descobrir quais vértices devem estar juntos em um bloco equivale a encontrar os componentes conectados do gráfico. Você pode fazer isso com uma pesquisa abrangente . Como a ordem inversa Cuthill-McKee de uma matriz é essencialmente uma pesquisa abrangente , provavelmente você pode encontrar o código Python de alguém para a ordem RCM e usá-lo diretamente ou modificá-lo para seus propósitos.

Daniel Shapero
fonte

Obrigado! Suponha que a matriz seja esparsa e simétrica (eremita).

Machine

Toda matriz é diagonal de bloco em uma sábia escolha de base - isso é chamado de forma normal de Jordan , e a base é composta de seus autovetores generalizados. Se a matriz é simétrica, essa base é composta de vetores próprios, e você pode calculá-la usando, por exemplo, o algoritmo QR . O SciPy fornece o módulo linalg.qrpara calcular as decomposições QR necessárias. Caso contrário, você pode usar a decomposição de valor singular , que pode ser calculada usando linalg.svd.

Christian Clason
fonte

Usar a forma normal da Jordânia é uma péssima idéia, pois é numericamente instável . Uma escolha melhor seria uma decomposição de Schur , numericamente estável, ao custo de reorganizar sua matriz em uma que seja triangular superior.

Geoff Oxberry

Claro, e eu não sugeri calculá-lo, exceto para matrizes simétricas, onde coincide com a decomposição de Schur (e pode ser calculada de maneira estável usando o algoritmo QR). Para matrizes não simétricas gerais, não conheço uma abordagem melhor para diagonalizar uma matriz que o SVD.

Christian Clason

E esse é um bom ponto. Eu não diria que o SVD "diagonaliza" uma matriz. Embora produza uma decomposição que contém uma matriz diagonal, a diagonalização é tradicionalmente usada para se referir a uma transformação de similaridade (ou uma decomposição com base em uma transformação / mudança de base) que resulta em uma matriz diagonal (ou diagonal de bloco). SVD não é uma transformação de similaridade, embora seja uma decomposição excepcionalmente útil.

precisa

Ponto tomado (e nesse sentido nem toda matriz é diagonalizável). Eu também apontaria que a diagonalização por uma transformação de similaridade não unitária pode ser muito instável.

Christian Clason