Em quais casos de aplicação os esquemas de pré-condicionamento aditivo são superiores aos multiplicativos?

12

Nos métodos de decomposição de domínio (DD) e multigrid (MG), pode-se compor a aplicação das atualizações de bloco ou correções grosseiras como aditivas ou multiplicativas . Para solucionadores pontuais, essa é a diferença entre as iterações de Jacobi e Gauss-Seidel. O mais suave multiplicativo para atuando como é aplicado como $Ax = b$ $S(x^{old}, b) = x^{new}$

$x_{i+1} = S_n(S_{n-1}( ..., S_1(x_i, b) ..., b), b)$

e o aditivo mais suave é aplicado como

$x_{i+1} = x_{i} + \displaystyle\sum_{\ell = 0}^{n}\lambda_\ell(S_\ell(x_i, b) - x_i)$

para algum amortecimento . O consenso geral parece ser o de que os multiplicadores têm propriedades de convergência muito mais rápidas, mas eu me perguntava: em que situações é melhor o desempenho das variantes aditivas desses algoritmos? $\lambda_i$

Mais especificamente, alguém tem algum caso de uso em que a variante aditiva deve e / ou apresenta desempenho significativamente melhor que a variante multiplicativa? Existem razões teóricas para isso? A maior parte da literatura sobre multigrid é bastante pessimista sobre o método Aditivo, mas é usada tanto no contexto do DD quanto o aditivo Schwarz. Isso também se estende à questão muito mais geral da composição de solucionadores lineares e não lineares, e que tipo de construção terá um bom desempenho e um bom desempenho em paralelo.

linear-algebra performance multigrid domain-decomposition Peter Brune
fonte

6

Os métodos aditivos expõem mais simultaneidade. Eles geralmente são apenas mais rápidos que os métodos multiplicativos, se você pode usar essa simultaneidade. Por exemplo, níveis grosseiros de multigrid geralmente são limitados à latência. Se você mover níveis grossos para subcomunicadores menores, eles poderão ser resolvidos independentemente dos níveis mais refinados. Com um esquema multiplicativo, todos os procs precisam esperar enquanto os níveis aproximados são resolvidos.

Além disso, se o algoritmo precisar de reduções em todos os níveis, a variante aditiva poderá coalescê-los onde o método multiplicativo for forçado a executá-los sequencialmente.

Jed Brown
fonte

Esta é a resposta que imaginei receber, então acho que vou ainda mais longe com a pergunta. Existem situações em que métodos aplicados de maneira aditiva, incluindo DD e MG, mas também divisão de campos (que podem ser considerados como DD, mas podem ter características diferentes na prática) ou a divisão de PDE são realmente melhores em termos de desempenho, robustez ou estabilidade do que a variante multiplicativa?

quer

1

As versões multiplicativas de muitos algoritmos precisam armazenar mais informações, mas às vezes convergem mais ou menos rápido. Às vezes, variantes aditivas são simétricas, mas pode ser muito mais trabalhoso tornar simétrico multiplicativo. Com a divisão do campo, o pré-condicionador pode se tornar mais aproximado quando você adiciona essas soluções extras. Podemos demonstrar isso com um exemplo do PETSc Stokes, se quiser. O aditivo é sempre mais fácil de vetorizar / mais simultâneo, mas qualquer ganho de desempenho é específico ao problema e à arquitetura.

Jed Brown

5

Para problemas de SPD, os métodos aditivos são melhores para a suavização de MG por várias razões, como já mencionado e mais algumas:

@Article{Adams-02, 
author = {Adams, M.~F. and Brezina, M. and Hu, J. J. and Tuminaro, R. S.}, 
title = {Parallel multigrid smoothing: polynomial versus {G}auss-{S}eidel}, 
journal = {J. Comp. Phys.}, 
year = {2003}, 
volume = {188}, 
number = {2}, 
pages = {593-610} }

Os métodos multiplicativos, no entanto, têm as propriedades espectrais corretas prontas para uso em um MG mais suave, ou seja, eles não precisam de amortecimento. Isso pode ser uma grande vitória para problemas hiperbólicos em que a suavização polinomial não é muito agradável.

Adams
fonte

0

Vou reafirmar o que @Jed disse: O método Multiplicativo sempre converge pelo menos tão bem como o método Aditivo (assintoticamente), para que você ganhe apenas com base na simultaneidade, mas isso depende da arquitetura.

Matt Knepley
fonte

Não tecnicamente correto, os espectros da matriz de iteração para, por exemplo, Gauss-Seidel não são uniformemente superiores a Jacobi (por exemplo, um valor próprio é morto com uma iteração de Jacobi). Mark (como faço para fazer logoff como Jed ...)

Jed Brown

Em quais casos de aplicação os esquemas de pré-condicionamento aditivo são superiores aos multiplicativos?

Respostas: