DEFLATION FOR THE OFF-DIAGONAL BLOCK IN SYMMETRIC SADDLE POINT SYSTEMS - Dumitrasc, Andrei; Kruse, Carola; Rüde, Ulrich (Siam Journal on Matrix Analysis and Applications, 2024)
Deflation techniques are typically used to shift isolated clusters of small eigenvalues in order to obtain a tighter distribution and a smaller condition number. Such changes induce a positive effect in the convergence behavior of Krylov subspace methods, which are among the most popular iterative solvers for large sparse linear systems. We develop a deflation strategy for symmetric saddle point matrices by taking advantage of their underlying block structure. The vectors used for deflation come from an elliptic singular value decomposition relying on the generalized Golub-Kahan bidiagonalization process. The block targeted by deflation is the off-diagonal one since it features a problematic singular value distribution for certain applications. One example is the Stokes flow in elongated channels, where the off-diagonal block has several small, isolated singular values, depending on the length of the channel. Applying deflation to specific parts of the saddle point system is important when using solvers such as CRAIG, which operates on individual blocks rather than the whole system. The theory is developed by extending the existing framework for deflating square matrices before applying a Krylov subspace method such as MINRES. Numerical experiments confirm the merits of our strategy and lead to interesting questions about using approximate vectors for deflation.
CRIS-Team Scopus Importer:2024-03-15
Keywords: eigenvalue deflation; Golub-Kahan bidiagonalization; saddle point problems; singular value decomposition; Stokes equation

Extensions of the Augmented Block Cimmino Method to the Solution of Full Rank Rectangular Systems - Dumitrasc, Andrei; Leleux, Philippe; Popa, Constantin; Rüde, Ulrich; Ruiz, Daniel (SIAM Journal on Scientific Computing, 2021)
For the solution of large sparse unsymmetric systems, Duff et al. [SIAM J. Sci. Comput., 37 (2015), pp. A1248–A1269] proposed an approach based on the block Cimmino iterations [Numer. Math., 35 (1980), pp. 1–12], in which the solution is computed in a single iteration, so we call it a pseudodirect solver. In this approach, matrices are augmented with additional variables and constraints so that a partitioning of the matrix in blocks of rows defines mutually orthogonal subspaces. The augmented system can then be solved efficiently with a sum of projections onto these orthogonal subspaces. The purpose of this manuscript is to extend this method to the minimum norm solution of underdetermined systems and to the solution of least-squares problems. In the latter case, a partitioning of the matrix in blocks of columns rather than rows is used, and the system must be suitably augmented to define mutually orthogonal subspaces again to recover the least-squares solution of the original problem. This article proves the equivalence between the solution of the original and the augmented system. In order to complete the extension to overdetermined systems, we also propose an iterative block conjugate gradient acceleration [SIAM J. Sci. Comput., 16 (1995), pp. 1478–1511] for the solution of least-squares problems. The efficiency of both the iterative and the augmented pseudodirect approaches, as implemented in the ABCD-Solver, is illustrated on large rectangular matrices from the SuiteSparse Matrix Collection. -We have learnt with great sadness that our co-author, long-term collaborator, advisor, and good friend Constantin Popa passed away while we were revising this article. We would like to dedicate this work to his memory.
Keywords: full rank linear systems; extended system; augmented block Cimmino; hybrid methods; least-squares problems; minimum norm solution

GENERALIZED GOLUB-KAHAN BIDIAGONALIZATION FOR NONSYMMETRIC SADDLE-POINT SYSTEMS - Dumitrasc, Andrei; Kruse, Carola; Rüde, Ulrich (Siam Journal on Matrix Analysis and Applications, 2025)
The generalized Golub-Kahan bidiagonalization has been used to solve saddle-point systems where the leading block is symmetric and positive definite. We extend this iterative method for the case where the symmetry condition no longer holds. We do so by relying on the known connection the algorithm has with the conjugate gradient method and following the line of reasoning that adapts the latter into the full orthogonalization method. We propose appropriate stopping criteria based on the residual and an estimate of the energy norm for the error associated with the primal variable. Numerical comparison with GMRES highlights the advantages of our proposed strategy regarding its low memory requirements and the associated implications.
CRIS-Team Scopus Importer:2025-02-28
Keywords: Golub-Kahan bidiagonalization; Krylov iterative methods; nonsymmetric saddle-point problems; Stokes equation

Inexact inner-outer Golub-Kahan bidiagonalization method: A relaxation strategy - Darrigrand, Vincent; Dumitrasc, Andrei; Kruse, Carola; Rüde, Ulrich (Numerical Linear Algebra With Applications, 2022)
We study an inexact inner-outer generalized Golub-Kahan algorithm for the solution of saddle-point problems with a two-times-two block structure. In each outer iteration, an inner system has to be solved which in theory has to be done exactly. Whenever the system is getting large, an inner exact solver is, however, no longer efficient or even feasible and iterative methods must be used. We focus this article on a numerical study showing the influence of the accuracy of an inner iterative solution on the accuracy of the solution of the block system. Emphasis is further given on reducing the computational cost, which is defined as the total number of inner iterations. We develop relaxation techniques intended to dynamically change the inner tolerance for each outer iteration to further minimize the total number of inner iterations. We illustrate our findings on a Stokes problem and validate them on a mixed formulation of the Poisson problem.
CRIS-Team WoS Importer:2022-12-30
Keywords: Golub–Kahan bidiagonalization; inner–outer iterative methods; saddle-point problems; Stokes equation