¿Se puede utilizar un método de subespacio de Krylov como un suavizador para multirredes?

15

Hasta donde yo sé, los solucionadores de múltiples cuadrículas usan suavizadores iterativos como Jacobi, Gauss-Seidel y SOR para amortiguar el error en varias frecuencias. ¿Se podría utilizar en su lugar un método de subespacio de Krylov (como gradiente conjugado, GMRES, etc.)? No creo que estén clasificados como "suavizantes", pero pueden usarse para aproximar la solución de rejilla gruesa. ¿Podemos esperar ver una convergencia análoga a la solución como lo haríamos en un método estándar de cuadrícula múltiple? ¿O depende del problema?

Paul
fuente

Respuestas:

18

Sí, puede, pero los métodos de Krylov generalmente no tienen excelentes propiedades de suavizado. Esto se debe a que se dirigen a todo el espectro de una manera adaptativa que minimiza el residuo o una norma adecuada del error. Esto generalmente incluirá algunos modos de baja frecuencia (longitud de onda larga) que las grillas gruesas habrían manejado bien. Los suavizadores de Krylov también hacen que el ciclo de multirredes no sea lineal, por lo que si se utiliza multirredes como preacondicionador para un método de Krylov externo, el método externo debe ser "flexible" (por ejemplo, GCR o FGMRES).

El uso de suavizadores de Krylov también aumenta en gran medida la cantidad de productos de punto que deben calcularse, lo que se convierte en un importante cuello de botella en paralelo. Sin embargo, incluso con estas propiedades poco atractivas, los suavizadores de Krylov a veces son útiles, especialmente para problemas difíciles en los que no están disponibles buenos operadores de interpolación.

Una alternativa más popular es utilizar suavizadores polinómicos (generalmente Chebyshev). Estos métodos se dirigen a una parte específica del espectro. Para PDE elípticas simétricas (donde el operador discreto es simétrico positivo definido o casi), es común estimar el mayor valor propio de D ^ {- 1} A donde D ^ {- 1} es el bloque de puntos Precondicionador de Jacobi para A y objetivo de un rango como (0.1 \ lambda _ {\ max}, 1.1 \ lambda _ {\ max}) . Los suavizadores polinomiales no tienen reducciones y son operaciones lineales (para cualquier grado polinomial elegido, generalmente elegido entre 1 y quizás 5 ). Por lo general, algunas iteraciones (digamos 5 a 10λmaxre-1UNre-1UN(0.1λmax,1.1λmax)15 55 510) de GMRES o CG se utilizan para estimar λmax , por lo que el usuario no necesita calcularlos por sí mismo. La estimación de λmax también es utilizada por algunos métodos algebraicos de múltiples cuadrículas para elegir estrategias de engrosamiento.

Adams, Brezina, Hu y Tuminaro (2003) es un buen artículo sobre el rendimiento paralelo y algorítmico de los suavizadores polinomiales. Tenga en cuenta que los suavizadores de polinomios tienden a ser menos efectivos (y / o difíciles de formular) para problemas no simétricos, en cuyo caso es probable que desee utilizar Gauss-Seidel o esquemas de relajación más sofisticados (bloqueo / distribución).

Jed Brown
fuente
¿Puede sugerir un buen recurso sobre polinomios y / o suavizadores de krylov? De hecho, nunca he oído hablar de ninguno :)
Paul
@JedBrown: ¿Te refieres a "elíptico" en el PDE o sentido de forma bilineal (es decir, ¿quieres decir que todos los valores propios del operador o símbolo principal son positivos?)? Supongo que esto último ya que estás hablando del punto de bloqueo Jacobi.
Jack Poulson
Paul agregué una referencia. @Jack Estrictamente hablando, el operador discreto debe ser SPD, pero en la práctica, los métodos tienden a funcionar siempre que el espectro no esté demasiado mal distribuido.
Jed Brown