Quais diretrizes devo seguir ao escolher um solucionador de sistema linear esparso?

49

Sistemas lineares esparsos aparecem com crescente frequência nas aplicações. Um deles tem muitas rotinas para escolher para resolver esses sistemas. No nível mais alto, existe um divisor de águas entre os métodos diretos (por exemplo, eliminação Gaussiana esparsa ou decomposição de Cholesky, com algoritmos especiais de ordenação e métodos multifrontais) e métodos iterativos (por exemplo, GMRES, (gradiente bi-) conjugado).

Como alguém determina se deve usar um método direto ou iterativo? Tendo feito essa escolha, como escolher um algoritmo específico? Eu já sei sobre a exploração da simetria (por exemplo, use gradiente conjugado para um sistema definido positivo simétrico esparso), mas existem outras considerações como essa a serem consideradas na escolha de um método?

JM
fonte

Respostas:

33

O importante na escolha de solucionadores iterativos é o espectro do operador, consulte este documento . No entanto, existem muitos resultados negativos; consulte este artigo em que nenhum solucionador iterativo vence para todos os problemas e este artigo em que eles provam que podem obter qualquer curva de convergência para o GMRES para qualquer espectro. Portanto, parece impossível prever o comportamento dos solucionadores iterativos, exceto em alguns casos isolados. Portanto, sua melhor opção é experimentar todos eles, usando um sistema como o PETSc , que também possui solucionadores diretos.

Matt Knepley
fonte
2
"Jogue tudo o que puder" era praticamente o conselho que eu estava acostumado. :) O terceiro artigo ao qual você vincula é algo que eu não tinha visto antes; obrigado por isso!
JM
2
Matt tem uma ótima resposta, mas você deve levá-la ao contexto da comunidade de onde ele vem (computação científica em larga escala). Você descobrirá que, para pequenos problemas (digamos, menos de cem mil desconhecidos), os solucionadores diretos superam amplamente os métodos iterativos, se o problema não for muito elíptico. Não vi nenhum artigo geral bom na literatura que o levasse a uma estratégia inicial inicial, o que é um pouco embaraçoso para mim.
Aron Ahmadia
5
A estimativa de Aron é boa, mas fortemente dependente do preenchimento, pois os métodos diretos esparsos geralmente esgotam a memória antes de esgotar a paciência.
Matt Knepley
18

A escolha entre métodos diretos e iterativos depende de objetivos e problemas em questão.

Para métodos Direct, podemos observar:

  • A matriz de coeficientes do sistema linear muda ao longo do cálculo e pode, para sistemas esparsos, esgotar os requisitos de memória e aumentar o esforço de trabalho devido ao preenchimento
  • É necessário concluir para fornecer resultados úteis
  • A fatoração pode ser reutilizada nas etapas subsequentes se houver vários lados do lado direito
  • Pode ser usado para resolver apenas sistemas lineares.
  • Raramente falha.

Para métodos iterativos, podemos observar:

  • O objetivo é fornecer um resultado parcial somente após um pequeno número de iterações.
  • O esforço da solução deve ser menor que os métodos diretos para o mesmo problema.
  • Econômico em relação ao armazenamento (sem preenchimento)
  • Geralmente fácil de programar.
  • Uma solução aproximada conhecida pode ser explorada.
  • Às vezes são rápidos e outras vezes não (às vezes até divergentes).
  • Para problemas complexos, os métodos iterativos são consideravelmente menos robustos em comparação aos métodos diretos.

Diretrizes para quando usar métodos diretos ou iterativos?

  • Métodos iterativos quando a matriz do coeficiente é escassa e os métodos diretos não podem explorar a escarsidade com eficiência (evite criar preenchimento).
  • Métodos diretos para vários lados do lado direito.
  • Métodos iterativos podem ser mais eficientes se a precisão for menos preocupante
  • Métodos iterativos para sistemas de equações não lineares.
Allan P. Engsig-Karup
fonte
8
Penso que é importante notar que os métodos diretos nem sempre são melhores para vários lados do lado direito. Talvez eles sejam melhores para lados direito, mas se o método iterativo for enquanto o método direto for , ainda é vantajoso usar o solucionador iterativo para lados direito. O ( n ) O ( n 2 ) O ( 1 )O(n)O(n)O(n2)O(1)
Jack Poulson
8

Concordo completamente com as respostas já dadas. Eu queria acrescentar que todos os métodos iterativos exigem algum tipo de palpite inicial. A qualidade desse palpite inicial geralmente pode afetar a taxa de convergência do método escolhido. Métodos como Jacobi, Gauss Seidel e Successful Over Relaxation trabalham para "suavizar iterativamente" o máximo de erros possível a cada etapa ( consulte este documento para obter detalhes) Os primeiros passos reduzem o erro de alta frequência rapidamente, mas o erro de baixa frequência leva muito mais tempo para ser suavizado. É isso que torna a convergência lenta para esses métodos. Em casos como esse, podemos acelerar a convergência resolvendo o erro de baixa frequência (por exemplo, resolvendo o mesmo problema em uma malha mais grossa) primeiro e depois resolvendo o erro de frequência mais alta (por exemplo, em uma malha mais fina). Se aplicarmos esse conceito recursivamente dividindo e conquistando, obteremos o que é chamado de método Multi-grid. Mesmo que o sistema linear não seja simétrico, existem implementações alternativas do método de grade múltipla para qualquer sistema de matriz esparsa não singular (por exemplo, método algébrico de grade múltipla) que pode acelerar a convergência do solucionador. Sua escalabilidade em sistemas paralelos, no entanto, é objeto de muitas pesquisas.

Paulo
fonte
5
Essa resposta parece dar a impressão de que a eficácia do multigrid vem de encontrar um bom palpite inicial. Na realidade, o palpite inicial é uma preocupação menor para problemas lineares e realmente apenas uma preocupação para o Multigrid completo. O multigrid trabalha devido à separação espectral. Observe que fazer com que o multigrid tenha um bom desempenho em problemas difíceis é um desafio significativo. O Multigrid funciona muito bem em paralelo, tem sido o ingrediente principal em vários prêmios Gordon Bell e alguns pacotes de código aberto são executados com alta eficiência nas maiores máquinas da atualidade. Para implementações de GPU, consulte a biblioteca CUSP.
precisa
Na maioria das vezes, um palpite inicial aleatório é bom o suficiente. Ao extrair autovalores usando o algoritmo de Lanczos, um vetor de inicialização / reinicialização aleatório ajuda. As reinicializações acontecem às vezes no algoritmo de Lanczos.
AnilJ
3

Falta uma informação importante na sua pergunta: de onde a matriz se originou. A estrutura do problema que você estava tentando resolver tem um grande potencial para sugerir um método de solução.

Se sua matriz se originou de uma equação diferencial parcial com coeficientes suaves, será difícil vencer um método geométrico multigrid, principalmente em três dimensões. Se o seu problema for menos regular, o multigrid algébrico é um bom método. Ambos geralmente combinados com métodos do espaço Krylov. Outros solucionadores eficientes podem ser derivados de métodos multipolares rápidos ou de transformada rápida de Fourier.

Guido Kanschat
fonte