Quais diretrizes devo usar ao procurar bons métodos de pré-condicionamento para um problema específico?

Para a solução de grandes sistemas lineares usando métodos iterativos, é frequentemente interessante introduzir o pré-condicionamento, por exemplo, resolva M - 1 ( A x = b ) , onde M é usado aqui para o pré-condicionamento à esquerda do sistema. Normalmente, devemos ter esse M - 1 ≈ A - 1 e fornecer a base para (muito mais) solução eficiente ou redução de recursos computacionais (por exemplo, armazenamento de memória) em comparação com a solução do sistema original (ou seja, quando M = $Ax=b$$M^{-1}(Ax=b)$$M$$M^{-1}\approx A^{-1}$$M=A$) No entanto, quais diretrizes devemos usar para escolher o pré-condicionador? Como os profissionais fazem isso para o seu problema específico?

Originalmente, eu não queria dar uma resposta porque isso merece um tratamento muito longo, e espero que alguém ainda o dê. No entanto, certamente posso dar uma breve visão geral da abordagem recomendada:

1. Faça uma pesquisa completa na literatura.
2. Se isso falhar, tente todos os pré-condicionadores que fizerem sentido para que você possa colocar as mãos em prática. MATLAB, PETSc e Trilinos são ambientes agradáveis ​​para isso.
3. Se isso falhar, você deve pensar cuidadosamente sobre a física do seu problema e verificar se é possível encontrar uma solução aproximada barata, talvez até uma versão ligeiramente alterada do seu problema.

Exemplos de 3 são as versões laplacianas deslocadas de Helmholtz, e o trabalho recente de Jinchao Xu sobre pré-condicionar o operador biharmonic com os laplacianos.

Outros já comentaram a questão do pré-condicionamento, o que chamarei de matrizes "monolíticas", ou seja, por exemplo, a forma discretizada de uma equação escalar, como a equação de Laplace, a equação de Helmholtz ou, se você deseja generalizar, o valor vetorial equação da elasticidade. Por essas coisas, fica claro que o multigrid (algébrico ou geométrico) é o vencedor se a equação é elíptica e, para outras equações, não é tão clara - mas algo como o SSOR geralmente funciona razoavelmente bem (para algum significado de "razoável").

Para mim, a grande revelação tem sido o que fazer com problemas que não são monolíticos, por exemplo, para o operador Stokes Quando comecei com a análise numérica, há 15 anos, acho que as pessoas tinham a esperança de que as mesmas técnicas pudessem ser aplicadas a essas matrizes, como acima, e a direção da pesquisa era tentar multigrid diretamente ou usar generalizações do SSOR (usando " smoothers de ponto "como Vanka) e métodos semelhantes. Mas isso desapareceu, pois não funciona muito bem.

$$\begin{pmatrix} A & B \\ B^T & 0 \end{pmatrix}.$$

O que veio substituir isso foi o que foi inicialmente chamado de "pré-condicionadores baseados na física" e mais tarde simplesmente (e talvez com mais precisão) "pré-condicionadores de bloco", como o de Silvester e Wathen. Geralmente, eles se baseiam na eliminação de blocos ou nos complementos de Schur e a idéia é criar um pré-condicionador de tal maneira que se possa reutilizar pré-condicionadores para blocos individuais que funcionam bem. No caso da equação de Stokes, por exemplo, o pré-condicionador de Silvester / Wathen usa que a matriz

$$\begin{pmatrix} A & B \\ 0 & B^T A^{-1} B \end{pmatrix}^{-1}$$ quando usado como pré-condicionador com GMRES resultaria em convergência em exatamente duas iterações. Por ser triangular, a inversão também é muito mais simples, mas ainda temos o problema do que fazer com os blocos diagonais, e aí se usa aproximações: onde o til significa substituir o inverso exato por uma aproximação. Isso geralmente é muito mais simples: como o bloco A é um operador elíptico, ~ A - 1 é bem aproximada por uma ciclo-V multigrade, por exemplo, e verifica-se que aqui, $$\begin{pmatrix} \widetilde{A^{-1}} & B \\ 0 & \widetilde{(B^T A^{-1} B)^{-1}} \end{pmatrix}$$ $A$$\widetilde{A^{-1}}$ é bem aproximado por uma ILU de uma matriz de massa.$\widetilde{(B^T A^{-1} B)^{-1}}$

Essa ideia de trabalhar com os blocos individuais que compõem a matriz e reutilizar pré-condicionadores em blocos individuais provou ser extremamente poderosa e mudou completamente a maneira como pensamos hoje nos sistemas de equações de pré-condicionamento. Obviamente, isso é relevante porque a maioria dos problemas reais são, de fato, sistemas de equações.

Jack deu um bom procedimento para encontrar um pré-condicionador. Vou tentar abordar a questão "O que faz um bom pré-condicionador?". A definição operacional é:

$A x = b$$M^{-1}$$A^{-1}$

no entanto, isso não nos dá uma ideia do design de um pré-condicionador. A maioria dos pré-condicionadores é baseada na manipulação do espectro do operador. Geralmente, os métodos de Krylov convergem mais rapidamente quando os valores próprios são agrupados, consulte Iterações de matriz ou funções meromorfas e álgebra linear . Às vezes, podemos provar que os resultados de um pré-condicionador são apenas alguns autovalores únicos, por exemplo, uma nota sobre pré-condicionamento para sistemas lineares indefinidos .

Uma estratégia comum é exemplificada pelo Multigrid. Pré-condicionantes relaxantes (aqui smoothers) como o SOR removem componentes de alta frequência no erro. Quando o resíduo é projetado em uma grade grosseira, os componentes de erro de frequência mais baixa se tornam uma frequência mais alta e podem ser atacados novamente pelo SOR. Essa estratégia básica está subjacente às versões mais complicadas do MG, como o AMG. Observe que, na parte inferior, o solucionador deve resolver as frequências mais baixas do erro com precisão.

Outra estratégia envolve resolver a equação em pequenos subespaços, exatamente o que os solucionadores de Krylov estão fazendo. Na forma mais simples, esse é o método Kaczmarz ou o Método Aditivo Schwarz . A tensão avançada da teoria aqui, Decomposição de Domínio , concentra-se na aproximação espectral do erro na interface, já que se supõe que os domínios sejam resolvidos com bastante precisão.

$A$