Adaptive control strategy for restarting GMRES

Abstract

El Residuo Mínimo Generalizado con reinicio, denominado GMRES(m), es utilizado generalmente para resolver sistemas de ecuaciones lineales de la forma Ax = b y tiene el inconveniente de presentar eventualmente en ciertos ciclos de reinicio un estancamiento o una tasa de convergencia lenta. Este trabajo presenta una formulación de control del GMRES(m) e introduce algunas estrategias de adaptación para evitar el estancamiento y acelerar el algoritmo de GMRES(m). Una regla de control cambia la estructura del GMRES(m) cuando se detecta el estancamiento y al mismo tiempo varía el parámetro de reinicio para modificar el subespacio Krylov. Esta estrategia hace que el control adaptativo sea competitivo desde el punto de vista de evitar el estancamiento y permitir la aceleración de la convergencia con respecto al número de iteraciones y el tiempo de cálculo. Por lo tanto, se observa que la versión de control adaptativo del GMRES(m) en la etapa apropia-da mejora la tasa de convergencia y robustez del método, incluso para los problemas difíciles. Los experimentos computacionales corroboran los resultados teóricos.

The Restarted Generalized Minimal Residual, denoted as GMRES(m), normally used for solving linear system of equations of the form Ax = b has the drawback of eventually presenting at certain re-starting cycles a stagnation or slowdown rate of convergence. This work presents the feedback control formulation for GMRES(m) and introduces some adaptive strategies to avoid the stagnation and speed up the algorithm of GMRES(m). A control rule changes the structure of the GMRES(m) when the stag-nation is detected and simultaneously varies the restarting parameter to modify the Krylov subspace. This strategy makes the adaptive control competitive from the point of view of avoiding the stagnation and acceleration the convergence with respect to the number of iterations and the computational time. Therefore, it is observed that the adaptive control version of GMRES(m) in the appropriate stage improves the rate of convergence and robustness even for the most difficult problems. Computational experiments corroborate the theoretical results.