Reorganizar una matriz ordinaria para bloquear la forma diagonal

¿Existe un algoritmo para reorganizar una matriz en forma de diagonal de bloque, dado que la matriz es de naturaleza diagonal de bloque pero aleatoria con una elección de base imprudente?

En particular, ¿hay algún módulo de Python para esto?

matrix python Máquina
fuente

¿Desea "reorganizar" la matriz mediante una permutación o un cambio de base?

Christian Clason

Originalmente tenía la intención de permutar la base que creo que es fácil de llevar a cabo. El caso de cambio de base se puede hacer tomando algún argumento físico si la matriz es hamiltoniana, pero para alguna matriz general, sería bastante difícil.

Máquina

Quizás te interese ¿Cómo puedo reestructurar matrices para tener elementos distintos de cero cerca de la diagonal?

Martin Thoma

Respuestas:

¿La matriz es escasa o densa? ¿Es simétrico?

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

El hecho de que su matriz sea (hasta una reordenación) diagonal de bloque significa que el gráfico no está conectado, y encontrar qué vértices deberían estar juntos en un bloque equivale a encontrar los componentes conectados del gráfico. Puede hacer esto con una búsqueda de amplitud . Dado que el orden inverso de Cuthill-McKee de una matriz es esencialmente una búsqueda de amplitud, probablemente pueda encontrar el código de Python de alguien para el pedido de RCM y usarlo directamente o modificarlo para sus propósitos.

Daniel Shapero
fuente

¡Gracias! Suponga que la matriz es escasa y simétrica (hermitiana).

Máquina

Cada matriz es diagonal de bloque en una sabia elección de base: esto se llama la forma normal de Jordan , y la base está compuesta por sus vectores propios generalizados. Si la matriz es simétrica, esta base está compuesta de vectores propios, y puede calcularla utilizando, por ejemplo, el algoritmo QR . SciPy proporciona el módulo linalg.qrpara calcular las descomposiciones QR necesarias. De lo contrario, podría usar la descomposición de valores singulares , que se puede calcular usando linalg.svd.

Christian Clason
fuente

Usar la forma normal de Jordan es una muy mala idea porque es numéricamente inestable . Una mejor opción sería una descomposición de Schur , que es numéricamente estable, a costa de reorganizar su matriz en una triangular superior.

Geoff Oxberry

Por supuesto, y no sugerí calcularlo a excepción de las matrices simétricas, donde coincide con la descomposición de Schur (y se puede calcular de manera estable utilizando el algoritmo QR). Para las matrices no simétricas generales, no conozco un mejor enfoque para diagonalizar una matriz que la SVD.

Christian Clason

Y ese es un buen punto. No diría que SVD "diagonaliza" una matriz. Si bien produce una descomposición que contiene una matriz diagonal, la diagonalización se usa tradicionalmente para referirse a una transformación de similitud (o una descomposición basada en dicha transformación / cambio de base) que da como resultado una matriz diagonal (o diagonal de bloque). SVD no es una transformación de similitud, aunque es una descomposición excepcionalmente útil.

Geoff Oxberry

Punto tomado (y en ese sentido no todas las matrices son diagonalizables). También señalaría que la diagonalización por una transformación de similitud no unitaria puede ser muy inestable.

Christian Clason