Invertendo uma matriz de banda

Eu tenho uma matriz de banda - uma matriz esparsa, quadrada e simétrica cuja estrutura se parece com a seguinte: $N \times N$

Aqui, a área sob as listras azuis são os elementos diferentes de zero; tudo o resto é zero

Existe um algoritmo para inverter esse tipo de matriz que é simples, mas mais eficiente que a eliminação gaussiana e a decomposição da LU?

algorithms linear-algebra sparse-matrices rnels12
fonte

Essas matrizes são chamadas de matrizes de banda (e, até onde eu sei, eram a motivação original para encontrar a largura de banda de um gráfico ), e possivelmente este artigo pode ser um ponto de partida útil.

G. Bach

@ G.Bach Obrigado, vou dar uma olhada no jornal. Você poderia me dizer a complexidade computacional do método?

usar o seguinte comando

Desculpe, não sei, pesquisei no Google por um minuto ou dois, mas pelo resumo parecia um começo promissor.

G. Bach

Deseja invertê-lo ou deseja resolver o sistema linear? A resposta é provavelmente a última, porque o inverso de uma matriz de banda é geralmente denso. Pergunta adicional: Existe mais estrutura para explorar?

Pseudônimo

ESTÁ BEM. A razão pela qual pergunto é que, na maioria dos casos, as pessoas que pensam que desejam inverter uma matriz provavelmente não o fazem. De qualquer forma, é uma boa pergunta!

Pseudônimo

Respostas:

Como nenhum dos comentários deu a resposta concreta, escreverei aqui explicitamente, caso alguém precise (como eu).

Em primeiro lugar, infelizmente, o inverso de uma matriz limitada por banda é uma matriz completa (não limitada por banda) em geral, portanto, basta preencher as entradas da matriz inversa. $\Omega\left(n^2\right)$ . Então, eu vou assumir que você só quer resolver um sistema linear $A x = b$ .

Usando o algoritmo deste artigo , uma matriz limitada de banda geral $A$ de tamanho $n \times n$ com largura de banda $k$ pode ser decomposto em triangular $k$ matrizes de largura de banda $L$ e $U$ no $O \left( k^2 n \right)$ Tempo. De lá, $L U x = b$ pode ser resolvido rapidamente $O(k n)$ Tempo. Então, no geral, o tempo de execução será $O\left(k^2 n\right)$ . Como acompanhamento, se $k$ é constante, isso significa que o sistema pode ser resolvido em tempo linear (altamente útil).

chausies
fonte