EVALUATING BLOCK PRECONDITIONERS IN THE SOLUTION OF SADDLE POINT SYSTEMS / Evaluación de Precondicionadores en Bloque

Résumé

ABSTRACT
This paper presents a new approach to precondition linear systems of the saddle point kind. Specifically we consider block diagonal, block triangular and block indefinite preconditioning techniques on nonsymmetric systems. These preconditioners require the computation of some inverses and we propose to use sparse approximate inverses (SPAI) to construct these approximations. The computation of these inverses involves solving a set of uncoupled least squares problems, which can be easily parallelized on a memory distributed machine. Comparison with other techniques suggests that block diagonal and block triangular preconditioning can be more effective if they are combined with SPAI techniques in the computation of approximate inverses. Results are promising and show the effectiveness of these preconditioners when improving the convergence of Krylov methods such as GMRES, which suggests the application of this approach in the large-scale setting.

RESUMEN
Este artículo presenta una nueva técnica para precondicionar sistemas lineales conocidos en la literatura como sistemas de punto de ensilladura. Específicamente consideramos precondicionadores en bloque del tipo diagonal, triangular e indefinido, sobre sistemas de punto de ensilladura no simétricos. Estos precondicionadores requieren el cálculo de inversas y proponemos usar la técnica de aproximación de inversa conocida como SPAI (Inverso aproximados escasa) por sus siglas en inglés. La construcción o cálculo de estas inversas requiere de la resolución de un conjunto de problemas desacoplados de mínimos cuadrados, que puede fácilmente paralelizarse en máquinas con memoria distribuida o máquinas vectoriales. Se presenta un análisis comparativo de tres precondicionadores propuestos. Los resultados numéricos muestran que los precondicionadores en bloque del tipo diagonal y triangular pueden ser más efectivos si se combinan con técnicas SPAI para el cálculo aproximado de las inversas, una vez que se mejoran sustancialmente las características de convergencia de métodos de Krylov como GMRES. Esto nos permite sugerir la aplicación de esta técnica en la resolución de sistemas de gran magnitud.
Palabras clave: Sistemas lineales de punto de ensilladura, Precondicionadores en bloque, Aproximación dispersa de inversas, Técnicas SPAI, Métodos de Krylov, GMRES.