turkmath.org

We propose a family of iterative schemes based on the null-space method for solving sparse linear systems with various saddle-point structures. The proposed schemes rely on the null-space method with sparse approximate null-space bases, followed by the factorized sparse approximate inverse preconditioner. The resulting preconditioned system becomes symmetric and positive definite or shifted skew-symmetric and can be solved via a Krylov subspace method, such as CG (Conjugate Gradient) or MRS (a minimal residual method for shifted skew-symmetric systems), respectively. CG and MRS are chosen for their robustness, reliance on short recurrences, and minimal number of inner products per iteration. Due to approximations, the proposed schemes involve a nested structure: outer-inner Krylov subspace methods and an innermost MRS solver or just CG. We show the robustness, memory consumption, and number of iterations of the proposed schemes for solving saddle-point linear systems that arise in various applications, such as optimization, computational fluid dynamics, optimal control, and circuit simulations, and compare them to classical preconditioned Krylov subspace methods. Finally, as future work, we expect the proposed schemes to have an advantage for parallelism, since the inner products are major bottlenecks for parallel performance because they create synchronization points. This is a joint work with Volker Mehrmann.