Pautas para preacondicionadores anidados

Considere la situación en la que desea resolver un sistema lineal utilizando un método de Krylov preacondicionado, pero aplicar el preacondicionador implica resolver un sistema auxiliar, que se realiza con otro método de Krylov preacondicionado.

• En un extremo, podría ejecutar la resolución interna a la convergencia dentro de cada paso de la resolución externa.

• En el otro extremo, no podría hacer la solución interna, sino reemplazarla con el preacondicionador interno.

• En algún lugar en el medio, podría truncar el bucle interno de Krylov después de un número fijo de iteraciones, o después de que se logre una cierta tolerancia.

Empíricamente, me he encontrado con situaciones en las que el primer extremo es mejor, y diferentes situaciones en las que el segundo extremo es mejor (en términos de costo total). Sin embargo, no puedo encontrar una razón clara de por qué ciertas situaciones favorecen una estrategia sobre otra.

¿Existe alguna orientación o teoría sobre cuándo son preferibles estas diferentes estrategias?

Esta pregunta ha estado abierta durante mucho tiempo, pero creo que aún merece ser respondida.

El problema fundamental con el uso de solucionadores de espacio Krylov en bloques individuales como preacondicionadores internos es que no son operadores lineales. Para entender esto, denotemos porel vector que obtienes como solución ejecutando un método de espacioK deKrylovKen el sistema linealAx=bpara a lo sumoNiteraciones o hasta quese alcanceuna toleranciaτ, utilizando un preacondicionadorP≈A-1. En otras palabras, puedes pensar en$\tilde x = K(A,P,\tau,N; b)$$K$$Ax=b$$N$$\tau$$P\approx A^{-1}$ como operador que actúa sobre b .$K$$b$

Ahora tenga en cuenta que es un operador lineal: requeriría resolver A x = b exactamente, es decir, K ( A , P , 0 , ∞ ; b ) = A - 1 b , que es lineal en b . En muchos casos, ejecutar un método de espacio de Krylov para exactamente una iteración a partir de un vector cero también es un operador lineal aplicado a$K(A,P,0,\infty;\cdot)$$Ax=b$$K(A,P,0,\infty;b)=A^{-1}b$$b$$b$$r^{(0)}=b-Ax^{(0)}$$K(A,P,\tau,N; \cdot)$$N$$\tau$

$K(A,P,\tau,N; \cdot)$$A$

Esto contrasta con muchos otros métodos que se usan para precondicionar: por ejemplo, un paso SSOR es una operación lineal en el vector al que lo aplica, al igual que todos los demás métodos que aplican un paso de una iteración de punto fijo.

El problema fundamental ahora es que la mayoría de los métodos espaciales de Krylov requieren que el preacondicionador sea un operador lineal. Simplemente no convergerán si el preacondicionador no es lineal, lo que explica su observación. Por otro lado, hay variaciones de algunos métodos espaciales de Krylov, generalmente precedidos por la palabra "Flexible", como F-GMRES en "GMRES Flexible", que funcionan alrededor de esto y que pueden tratar con preacondicionadores que no son lineales operadores. Estas variantes flexibles de los métodos originales seguirán convergiendo, y a menudo son métodos poderosos cuando se combinan con preacondicionadores buenos (pero no lineales).