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

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?

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.

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.

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.

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.