Segregated iterative linear solvers for saddle-point systems based on bidiagonalization

The aim of this work is to define and refine iterative linear solvers applied to saddle-point problems, with a special emphasis on generalized CRAIG and Golub-Kahan bidiagonalization (GKB). The first topic that we approach is that of deflation, a technique which we employ to shift small spectral outliers in order to obtain a tighter clustering and a smaller condition number for the system matrix, leading to faster solver convergence. Our objective is to outline a segregated deflation strategy that can benefit generalized CRAIG, our linear solver of choice for symmetric saddle-point problems. We start by defining the necessary deflation steps and matrices under the assumption of an exact elliptic singular value decomposition. We then proceed in a more practical direction by relaxing the assumption and working instead with approximate triplets which can be found by the two iterative procedures we propose. Finally, we explore how our deflation and preconditioning interact when solving a test case problem of Stokes flow and compare our segregated deflation scheme against the existing monolithic alternative that can be paired with the Minimal Residual (MINRES) solver. The second topic we consider takes a deeper look into the generalized GKB, namely into its inner problem which is itself a linear system. The theory leading to the original algorithm requires a matrix-vector product with an inverse, operation which, for maximum accuracy, is implemented as a call to a direct solver. For large problems however, these solvers can require a prohibitively large amount of memory, which is why we consider iterative methods instead. Our numerical study explores how the solution of the outer problem depends on that of the inner one, which opens more possibilities for scenarios where we are only interested in moderately accurate approximations. We further show how each inner solve can be increasingly cheaper by dynamically decreasing the accuracy without a negative impact on the final iterate. Our aim is to minimize the cost, which we define as the total number of inner iterations accumulated over all the outer ones. We find that adaptive accuracy can reduce this number by 30% on its own and by 50% if the problem is treated beforehand by a method like preconditioning or deflation. The third and final part of this work is devoted to extending the generalized GKB and its associated CRAIG solver in a way that allows them to tackle nonsymmetric saddle-point systems. Our starting point is a known equivalence between CRAIG and Conjugate Gradient (CG), which we adapt to describe our proposed solver and Full Orthogonalization Method (FOM) instead. We show that our solver has interesting properties, the most notable of which is the comparatively low memory requirement. We illustrate our findings on a linearized Navier-Stokes and consider (preconditioned) Generalized Minimal Residual (GMRES) for our numerical comparisons. One of these findings is that our solver can converge significantly faster with at least 10 times less memory than a GMRES of similar complexity.