¿Es habitual no tener comprobación de convergencia en Multigrid?

12

Acabo de leer el Capítulo 3 en "Un tutorial de múltiples cuadrículas" de Briggs / Henson / McCormick, enlace .

El texto trata sobre ciclos de cuadrícula múltiple como V-cycle, mu-cycle, FMG. Lo que me llamó la atención: en la mayoría de los procedimientos iterativos, uno verifica si ha convergido a la tolerancia / precisión deseada y, de ser así, el procedimiento se detiene. Pero Briggs / Henson / McCormick no utilizan ninguna comprobación de convergencia en los esquemas presentados. El número de iteraciones y recursiones solo está codificado y uno tiene que confiar en que el esquema convergerá.

Entonces, ¿cómo se hace esto en Multigrid normalmente? ¿Es habitual que el número de iteraciones / recursiones solo esté codificado? Realmente me temo que malgastaré mucho tiempo de cálculo porque soy demasiado preciso o, por otro lado, la precisión será pobre en muchos casos cuando elijo un número menor de iteraciones / recursiones.

Miguel
fuente
La falta de respuestas a esta pregunta es realmente sorprendente para mí. ¿Seguramente hay algunos usuarios muy activos aquí que tienen bastante experiencia en múltiples cuadrículas en entornos de investigación y / o producción?
Doug Lipinski
2
Creo que el problema es que hoy en día las multirredes rara vez se usan como un solucionador en sí mismo (debido a la falta de teoría de convergencia general, creo), sino más bien como un preacondicionador para un método iterativo más establecido como CG o GMRES. En este contexto, no es necesaria una verificación de convergencia para multirredes, ya que la iteración externa se encarga de ello.
Christian Clason

Respuestas:

4

Sí, es normal no tener controles de convergencia en MG por varias razones. Primero, si usa un número diferente de iteraciones en cada pasada, entonces el operador MG ya no es lineal, y tendría que usar algo como FGMRES como acelerador que puede acomodar un preacondicionador no lineal. En segundo lugar, FMG es un solucionador exacto (reduce el error por debajo del error de discretización) cuando funciona, por lo que verificar la convergencia introduce una sincronización costosa en el algoritmo. Generalmente verificaría al final solo para verificar la convergencia.

Matt Knepley
fuente
¿Tienes alguna fuente para respaldar esto? Actualmente, su respuesta y la otra respuesta más votada se contradicen directamente entre sí.
Doug Lipinski
1) El libro de Saad es la mejor referencia para usar FGMRES para acomodar un preacondicionador cambiante: www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf 2) Creo que la prueba de que FMG reduce el error por debajo del error de discretización con un poder suficientemente potente V-cycle está en Trottenberg y Osterlee, pero reproduzco la prueba en mi libro: cse.buffalo.edu/~knepley/classes/caam519/CSBook.pdf
Matt Knepley
4

Definitivamente no. Para elegir un ejemplo, el libro Multigrid tiene un gráfico en la página 53 (Figura 2.10) que muestra la disminución en el residual en función del número de ciclos V o W. Dejaría de andar en bicicleta cuando esté satisfecho con el tamaño del residuo.

La fuente de su confusión puede deberse a que algunas descripciones solo describen un solo ciclo V. En algunos casos limitados, debido a que la cuadrícula múltiple es una técnica tan poderosa, esto puede generar una solución adecuada. Además, multigrid se puede utilizar como preacondicionador . En ese caso, la cuadrícula múltiple es solo un acelerador, y la verificación de convergencia ocurre en un nivel superior. Pero el cheque siempre debe ocurrir en algún lugar.

Acero de Damasco
fuente
1
¿Tienes alguna fuente para respaldar esto? Actualmente, su respuesta y la otra respuesta más votada se contradicen directamente entre sí.
Doug Lipinski
1

En Multigrid utilizado como solucionador , generalmente la norma relativa del residuo se utiliza como criterio de detención. A medida que disminuye esta proporción, la precisión de la solución debería aumentar. Además, al nivel más grueso, los investigadores hacen cosas diferentes:

  1. resuelva usando un solucionador directo (sin convergencia)
  2. usar iteraciones fijas (sin convergencia)
  3. use la diferencia sucesiva entre iteraciones como criterio de convergencia (no es un buen método porque podría estar muy lejos de la solución)
  4. Nuevamente use la norma relativa de residuos como criterio de detención.

Método 2 mencionados anteriormente en el nivel más grueso es bueno cuando Multigrilla se utiliza como un pre-acondicionado (multigrid expertos aquí puede comentar - Soy un principiante).

Entonces, en general se usa la convergencia .

Gaurav Saxena
fuente