Quando é fácil inverter uma matriz esparsa?

Question

( Crossposted em cstheory.SE)

Quando é fácil inverter uma matriz esparsa? Especificamente, estou me perguntando sobre os casos em que a inversão de matriz tem custo semelhante à multiplicação de matriz esparsa, portanto, custo muito menor do que a inversão de matriz completa.

Se o padrão de não zeros corresponder a um gráfico de largura de árvore limitada, a inversão exata é linear no número de não zeros.

Para largura de árvore ilimitada, mas matriz diagonalmente dominante, os algoritmos de Gauss-Seidel e Jacobi convergem exponencialmente rápido. Para uma classe maior de matrizes "somadas por caminhada" (que restringe a magnitude das entradas fora da diagonal), a propagação da crença gaussiana converge exponencialmente rápido (mas fornece uma estimativa tendenciosa do inverso).

Quais são as outras condições interessantes para fácil invertibilidade além da largura da árvore / dominância diagonal?

Answer 1

Um desses casos é se a matriz esparsa estiver em faixas. Por exemplo, sistemas lineares tridiagonais podem ser resolvidos em tempo linear usando o algoritmo de Thomas. Para larguras de banda pequenas, você pode encontrar um algoritmo de custo de tempo linear. Observe que, conforme a largura de banda aumenta, o coeficiente oculto também aumenta.

A literatura sobre o assunto é ativa e há muitas caracterizações, pelo que vejo, algumas das quais você já encontrou. Talvez você deva adicionar solicitação de referência como uma tag.

Answer 2

Existem muitas maneiras de resolver sistemas com matrizes esparsas, portanto não há como responder definitivamente e esgotar todas as possibilidades. No entanto, adicionarei os métodos de Krylov como uma resposta. Muitos métodos de Krylov alcançam resultados rápidos nas condições certas.

As condições para os métodos de Krylov funcionarem bem já foram perguntadas aqui antes . Cada solucionador Krylov é um pouco diferente, mas darei o GMRES como exemplo.

Para GMRES, se sua matriz de entrada tiver as seguintes propriedades:

1. Normal (ou aproximadamente normal)
2. Valores próprios não muito próximos de 0
3. Agrupamento de autovalores ("grupos" facilmente identificados de autovalores todos próximos)

então GMRES provavelmente convergirá muito rapidamente, independentemente do vetor do lado direito. Observe que as condições de (1) a (3) na verdade não dizem nada sobre a esparsidade da matriz, mas geralmente, como o produto matriz-vetor esparso é barato, o algoritmo GMRES pode ser bem adequado para o caso esparso.