En métodos como gmres o bicgstab, podría ser atractivo utilizar otro método krylov como preacondicionador. Después de todo, son fáciles de implementar de forma libre de matriz y en un entorno paralelo. Por ejemplo, uno podría usar algunas (digamos ~ 5) iteraciones de bigcstab sin preacondicionar como precontionador para gmres, o cualquier otra combinación de métodos krylov. No encuentro mucha referencia a este enfoque en la literatura, por lo que espero que esto se deba a que no es muy efectivo. Me gustaría entender por qué no es eficiente. ¿Hay casos en los que es una buena opción?
En mi investigación, estoy interesado en la solución de problemas elípticos en 3D en un entorno paralelo (mpi).
linear-algebra
linear-solver
preconditioning
krylov-method
gmres
Christine Darcoux
fuente
fuente
Respuestas:
Es interesante que esta pregunta surgiera ayer, ya que ayer acabo de terminar una implementación que hace esto.
Mi pasado
Para empezar, hágame saber que, aunque mi formación académica es de informática científica, todo el trabajo que he realizado desde que me gradué, incluido mi doctorado actual. trabajo, ha estado en electromagnetismo computacional. Entonces, supongo que nuestros antecedentes son algo similares, ya que también parece que estás mirando la física (según tu perfil).
FGMRES
En primer lugar, lo que está buscando, como Guido Kanschat ya ha mencionado en un comentario, se llama GMRES flexible o FGMRES. La referencia, incluido el pseudocódigo, está en [1]. Si bien a veces encuentro que los documentos numéricos de SIAM son un poco difíciles de leer, [1] (y la mayoría del otro trabajo de Saad, incluido el brillante [B1], aparentemente disponible legalmente en línea gratis) es diferente; El documento es una lectura fascinante, muy claramente escrita y con algunos buenos ejemplos y sugerencias para las aplicaciones.
FGMRES es fácil de implementar, especialmente si ya tiene un GMRES preacondicionado DERECHO en funcionamiento. Tenga en cuenta la palabra clave DERECHA aquí: si tiene un GMRES preacondicionado IZQUIERDO, es decir, está acostumbrado a resolver MAx = Mb, entonces tiene que hacer algunas modificaciones. Compare [B1, Algoritmo 9.4 en la pág. 282] a [B1, Algoritmo 9.5, pág. 284]. También puede encontrar los FGMRES en [B1, Algoritmo 9.6, pág. 287], pero realmente te animo a leer [1] ya que es breve, bien escrito y aún tiene muchos detalles interesantes.
Qué hace
Básicamente, FGMRES le permite cambiar los preacondicionadores para cada iteración, si lo desea. Una de las aplicaciones para esto es que puede usar algún preacondicionador que funciona muy bien cuando está lejos de la solución, y luego cambiar a otro cuando se acerque. [2], que no he leído en detalle, parece discutir algo similar a esto.
Sin embargo, la aplicación más interesante en mi caso fue que podía usar un GMRES (preacondicionado) como preacondicionador para sus FGMRES. Esta es la razón detrás del nombre típico de FGMRES, "GMRES interno-externo". Aquí, "externo" se refiere al solucionador FGMRES, que (como preacondicionador) utiliza un solucionador "interno".
Entonces, ¿qué tan bueno es esto en la práctica?
En mi caso, esto funcionó absolutamente brillante. En el ciclo interno, "resuelvo" una formulación de mi problema de complejidad reducida. Por sí sola, esta solución es demasiado imprecisa para nuestro uso, pero funciona absolutamente bien como preacondicionador. Tenga en cuenta la resolución "" alrededor ": no es necesario ejecutar el solucionador interno hasta la convergencia, ya que solo está buscando aproximaciones aproximadas. En mi caso, pasé de usar 151 iteraciones, cada una con un costo de 64 segundos, a 72 iteraciones, cada una con un costo de 79 segundos (usé 5 iteraciones fijas en el GMRES interno). Eso es un ahorro total de una hora, sin pérdida de precisión y muy poco trabajo de codificación ya que ya teníamos un GMRES funcional que acabamos de hacer recursivo.
Para algunas aplicaciones de estas cosas, que demuestran el rendimiento potencial, consulte [3] (que en realidad usa un FGMRES de tres niveles, por lo que FGMRES, con FGMRES como interno, con GMRES como interno-interno) y [4], que también podría ser aplicación específica para su uso, pero contiene varios casos de prueba interesantes.
Referencias
[1] Y. Saad, "Un algoritmo GMRES precondicionado flexible interno-externo", SIAM J. Sci. Comp., Vol. 14, no. 2, págs. 461–469, marzo de 1993. http://www-users.cs.umn.edu/~saad/PDF/umsi-91-279.pdf
[2] D.-Z. Ding, R.-S. Chen y Z. Fan, "Método GMRES flexible interno-externo precondicionado SSOR para el análisis MLFMM de dispersión de objetos abiertos", Progress In Electromagnetics Research, vol. 89, págs. 339–357, 2009. http://www.jpier.org/PIER/pier89/22.08112601.pdf
[3] TF Eibert, "Algunos resultados de dispersión calculados por ecuación integral de superficie y técnicas híbridas integrales de límite de elementos finitos, acelerados por el método multipolar rápido multinivel", IEEE Antennas and Propagation Magazine, vol. 49, no. 2, págs. 61-69, 2007.
[4] Ö. Ergül, T. Malas y L. Gürel, "Soluciones de problemas de electromagnetismo a gran escala utilizando un esquema iterativo interno-externo con algoritmos multipolares rápidos multinivel ordinarios y aproximados", Progress In Electromagnetics Research, vol. 106, págs. 203–223, 2010. http://www.jpier.org/PIER/pier106/13.10061711.pdf
[B1] Y. Saad, Métodos iterativos para sistemas lineales dispersos. SIAM, 2003. http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf
fuente
Tal método de subespacio de Krylov anidado puede funcionar bastante bien en la práctica. Puede ser de interés para sistemas lineales no simétricos para los que GMRES reiniciado se estanca y GMRES no reiniciado es demasiado costoso o usa demasiada memoria. Alguna literatura:
fuente