Como se pode paralelizar um método multigrid para resolver um sistema linear de equações?

Pelo que entendi, o método multigrid resolve um sistema linear, resolvendo uma versão mais grossa do mesmo problema (eliminando o erro de baixa frequência) e projetando-se de volta à grade fina para suavizar os erros de alta frequência. Para sistemas grandes, posso ver como um método iterativo pode ser implementado em paralelo em cada nível de grade. Essa abordagem escala bem em paralelo? Existe alguma outra fonte de simultaneidade no algoritmo que se possa explorar em paralelo?

O multigrid geométrico paralelo é fácil de implementar em grades estruturadas. Multigrid algébrico e não estruturado são mais técnicos; consulte esta resposta para obter links para implementações.

$V$$\log_{c} N$$N$2 d 3 d d log 2 log c$c$$2^d$$3^d$$d$$\log_2 \log_c N$

Gauss-Seidel é um material muito mais suave, que é multiplicativo e parece não ter um paralelo eficiente. Para discretizações simples em grades estruturadas e quando a largura de banda da memória não é uma preocupação, a solução clássica do Gauss-Seidel vermelho-preto é razoável. Para problemas mais complexos e em hardware moderno, Adams (2001) mostra um algoritmo muito mais eficiente. Para muitos problemas, a abordagem simples de usar Gauss-Seidel independente em cada subdomínio é totalmente satisfatória. Uma alternativa a Gauss-Seidel é usar as irmãs Jacobi ou polinomiais amortecidas, veja Adams, Brezina, Hu e Tuminaro (2003) para uma comparação. O modelo de desempenho para essas smoothers é semelhante a qualquer outro cálculo de estêncil e, portanto, possui uma escalabilidade fraca ideal,$\mathcal O (N/P)$ para subdomínios grandes o suficiente para cobrir a latência.

Na prática, as grades grossas atingem rapidamente o forte limite de escalabilidade (além do qual a adição de mais processos aumenta o tempo de execução), portanto elas devem residir em comunicadores MPI cada vez menores. Isso adiciona alguma complexidade leve à implementação. Para problemas nos quais os níveis grossos têm estrutura demais para continuar a crescer, a resolução do nível grosso pode se tornar um gargalo.

Para testar vários métodos paralelos multigrid, eu recomendo o uso de uma biblioteca como o PETSc, que permite executar muitos algoritmos diferentes com muito pouco código de usuário.