Invertir una matriz de banda

Tengo una matriz de banda : una matriz escasa, cuadrada y simétrica cuya estructura se parece a la siguiente: $N \times N$

Aquí, el área debajo de las rayas azules son los elementos distintos de cero; todo lo demás es cero

¿Existe algún algoritmo para invertir este tipo de matriz que sea simple pero más eficiente que la eliminación gaussiana y la descomposición de LU?

algorithms linear-algebra sparse-matrices rnels12
fuente

Esas matrices se llaman matrices de banda (y que yo sepa, fueron la motivación original para encontrar el ancho de banda de un gráfico ), y posiblemente este documento podría ser un punto de partida útil.

G. Bach

@ G.Bach Gracias, echaré un vistazo al periódico. ¿Podría decirme la complejidad computacional del método?

rnels12

Lo siento, no sé, busqué en Google por un minuto o dos, pero desde el resumen parecía un comienzo prometedor.

G. Bach

¿Quieres invertirlo o quieres resolver el sistema lineal? La respuesta es probablemente la última, porque la inversa de una matriz de banda suele ser densa. Pregunta adicional: ¿Hay más estructura para explotar?

Seudónimo

OKAY. La razón por la que pregunto es que, en la mayoría de los casos, las personas que piensan que desean invertir una matriz probablemente no lo hacen. De cualquier manera, ¡es una buena pregunta!

Seudónimo

Respuestas:

Dado que ninguno de los comentarios dio la respuesta concreta, lo escribiré explícitamente aquí en caso de que alguien lo necesite (como yo lo hice).

En primer lugar, desafortunadamente, el inverso de una matriz de banda limitada es una matriz completa (sin banda limitada) en general, por lo que solo completar las entradas de la matriz inversa tomaría . Así que supondré que solo quieres resolver un sistema lineal . $\Omega\left(n^2\right)$ $A x = b$

Usando el algoritmo en este documento , una banda-limitado matriz general de tamaño con ancho de banda se pueden descomponer en triangular -bandwidth matrices y en tiempo. A partir de ahí, se puede resolver rápidamente en el tiempo . Entonces, en general, el tiempo de ejecución será . Como seguimiento, si es constante, eso significa que el sistema se puede resolver en tiempo lineal (muy útil). $A$ $n \times n$ $k$ $k$ $L$ $U$ $O \left( k^2 n \right)$ $L U x = b$ $O(k n)$ $O\left(k^2 n\right)$ $k$

chausies
fuente