A class of generalized shift-splitting preconditioners for nonsymmetric saddle point problems

In this paper, a class of generalized shift-splitting preconditioners with two shift parameters are implemented for nonsymmetric saddle point problems with nonsymmetric positive definite (1, 1) block. The generalized shift-splitting (GSS) preconditioner is induced by a generalized shift-splitting of the nonsymmetric saddle point matrix, resulting in an unconditional convergent fixed-point iteration. By removing the shift parameter in the (1, 1) block of the GSS preconditioner, a deteriorated shift-splitting (DSS) preconditioner is presented. Some useful properties of the DSS preconditioned saddle point matrix are studied. Finally, numerical experiments of a model Navier–Stokes problem are presented to show the effectiveness of the proposed preconditioners.     

A modified generalized shift-splitting preconditioner for nonsymmetric saddle point problems

For the nonsymmetric saddle point problems with nonsymmetric positive definite (1,1) parts, the modified generalized shift-splitting (MGSS) preconditioner as well as the MGSS iteration method is derived in this paper, which generalize the modified shift-splitting (MSS) preconditioner and the MSS iteration method newly developed by Huang and Su (J. Comput. Appl. Math. 317:535–546, 2017), respectively. The convergent and semi-convergent analyses of the MGSS iteration method are presented, and we prove that this method is unconditionally convergent and semi-convergent. Meanwhile, some spectral properties of the preconditioned matrix are carefully analyzed. Numerical results demonstrate the robustness and effectiveness of the MGSS preconditioner and the MGSS iteration method and also illustrate that the MGSS iteration method outperforms the generalized shift-splitting (GSS) and the generalized modified shift-splitting (GMSS) iteration methods, and the MGSS preconditioner is superior to the shift-splitting (SS), GSS, modified SS (M-SS), GMSS and MSS preconditioners for the generalized minimal residual (GMRES) method for solving the nonsymmetric saddle point problems.     

Variable parameter Uzawa method for solving a class of block three-by-three saddle point problems

In this work, we consider numerical methods for solving a class of block three-by-three saddle point problems, which arise from finite element methods for solving time-dependent Maxwell equations and a class of quadratic programs. We present a variant of Uzawa method with two variable parameters for the saddle point problems. These two parameters can be updated easily in each iteration, similar to the evaluation of the two iteration parameters in the conjugate gradient method. We show that the new iterative method converges to the unique solution of the saddle point problems under a reasonable condition. Numerical experiments highlighting the performance of the proposed method for problems are presented.

     

Symmetric-triangular decomposition and its applications part II: Preconditioners for indefinite systems

As an application of the symmetric-triangular (ST) decomposition given by Golub and Yuan (2001) and Strang (2003), three block ST preconditioners are discussed here for saddle point problems. All three preconditioners transform saddle point problems into a symmetric and positive definite system. The condition number of the three symmetric and positive definite systems are estimated. Therefore, numerical methods for symmetric and positive definite systems can be applied to solve saddle point problems indirectly. A numerical example for the symmetric indefinite system from the finite element approximation to the Stokes equation is given. Finally, some comments are given as well. AMS subject classification (2000) 65F10     

Block and joint ℋ︁-matrix preconditioners for the Oseen equations

For saddle point problems in fluid dynamics, many preconditioners in the literature exploit the block structure of the problem to construct block diagonal or block triangular preconditioners. The performance of such preconditioners depends on whether fast, approximate solvers for the linear systems on the block diagonal as well as for the Schur complement are available. We will construct these efficient preconditioners using hierarchical matrix techniques in which fully populated matrices are approximated by blockwise low rank approximations. We will compare such block preconditioners with those obtained through a completely different approach where the given block structure is not used but a domain-decomposition based ℋ︁-LU factorization is constructed for the complete system matrix. Preconditioners resulting from these two approaches will be discussed and compared through numerical results. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Evaluation of ST preconditioners for saddle point problems

The general block ST decomposition of the saddle point problem is used as a preconditioner to transform the saddle point problem into an equivalent symmetric and positive definite system. Such a decomposition is called a block ST preconditioner. Two general block ST preconditioners are proposed for saddle point problems with symmetric and positive definite (1,1)-block. Some estimations of the condition number of the preconditioned system are given. The same study is done for singular (1,1)-block.     

On parameterized block triangular preconditioners for generalized saddle point problems

In this paper, we discuss two classes of parameterized block triangular preconditioners for the generalized saddle point problems. These preconditioners generalize the common block diagonal and triangular preconditioners. We will give distributions of the eigenvalues of the preconditioned matrix and provide estimates for the interval containing the real eigenvalues. Numerical experiments of a model Stokes problem are presented.     

An improved lower bound on a positive stable block triangular preconditioner for saddle point problems

In this paper, a new lower bound on a positive stable block triangular preconditioner for saddle point problems is derived; it is superior to the corresponding result obtained by Cao [Z.-H. Cao, Positive stable block triangular preconditioners for symmetric saddle point problems, Appl. Numer. Math. 57 (2007) 899–910]. A numerical example is reported to confirm the presented result.     

On block preconditioners for saddle point problems with singular or indefinite (1, 1) block

We discuss a class of preconditioning methods for the iterative solution of symmetric algebraic saddle point problems, where the (1, 1) block matrix may be indefinite or singular. Such problems may arise, e.g. from discrete approximations of certain partial differential equations, such as the Maxwell time harmonic equations. We prove that, under mild assumptions on the underlying problem, a class of block preconditioners (including block diagonal, triangular and symmetric indefinite preconditioners) can be chosen in a way which guarantees that the convergence rate of the preconditioned conjugate residuals method is independent of the discretization mesh parameter. We provide examples of such preconditioners that do not require additional scaling. Copyright © 2010 John Wiley & Sons, Ltd.     

A class of block alternating splitting implicit iteration methods for double saddle point linear systems

In the framework of a special block alternating splitting implicit (BASI) iteration scheme for generalized saddle point problems, we establish some new iteration methods for solving double saddle point problems by means of a suitable partitioning strategy. Convergence analysis of the corresponding BASI iteration methods indicates that they are convergent unconditionally under certain weak requirements for the related matrix splittings, which are satisfied directly for our specific application to double saddle point problems. Numerical examples for liquid crystal director and time-harmonic eddy current models are presented to demonstrate the efficiency of the proposed BASI preconditioners to accelerate the GMRES method.     

Optimization of the parameterized Uzawa preconditioners for saddle point matrices

The parameterized Uzawa preconditioners for saddle point problems are studied in this paper. The eigenvalues of the preconditioned matrix are located in (0, 2) by choosing the suitable parameters. Furthermore, we give two strategies to optimize the rate of convergence by finding the suitable values of parameters. Numerical computations show that the parameterized Uzawa preconditioners can lead to practical and effective preconditioned GMRES methods for solving the saddle point problems.     

Block diagonally preconditioned PIU methods of saddle point problem

For large sparse saddle point problems, we firstly introduce the block diagonally preconditioned Gauss-Seidl method (PBGS) which reduces to the GSOR method [Z.-Z. Bai, B.N. Parlett, Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math. 102 (2005) 1-38] and PIU method [Z.-Z. Bai, Z.-Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl. 428 (2008) 2900-2932] when the preconditioners equal to different matrices, respectively. Then we generalize the PBGS method to the PPIU method and discuss the sufficient conditions such that the spectral radius of the PPIU method is much less than one. Furthermore, some rules are considered for choices of the preconditioners including the splitting method of the (1, 1) block matrix in the PIU method and numerical examples are given to show the superiority of the new method to the PIU method.     

A comparison of overlapping Schwarz methods and block preconditioners for saddle point problems

Three domain decomposition methods for saddle point problems are introduced and compared. The first two are block‐diagonal and block‐triangular preconditioners with diagonal blocks approximated by an overlapping Schwarz technique with positive definite local and coarse problems. The third is an overlapping Schwarz preconditioner based on indefinite local and coarse problems. Numerical experiments show that while all three methods are numerically scalable, the last method is almost always the most efficient. Copyright © 2000 John Wiley & Sons, Ltd.     

On the eigenvalues of a class of saddle point matrices

We study spectral properties of a class of block 2 × 2 matrices that arise in the solution of saddle point problems. These matrices are obtained by a sign change in the second block equation of the symmetric saddle point linear system. We give conditions for having a (positive) real spectrum and for ensuring diagonalizability of the matrix. In particular, we show that these properties hold for the discrete Stokes operator, and we discuss the implications of our characterization for augmented Lagrangian formulations, for Krylov subspace solvers and for certain types of preconditioners. The work of this author was supported in part by the National Science Foundation grant DMS-0207599 Revision dated 5 December 2005.     

Preconditioning discretizations of systems of partial differential equations

This survey paper is based on three talks given by the second author at the London Mathematical Society Durham Symposium on Computational Linear Algebra for Partial Differential Equations in the summer of 2008. The main focus will be on an abstract approach to the construction of preconditioners for symmetric linear systems in a Hilbert space setting. Typical examples that are covered by this theory are systems of partial differential equations which correspond to saddle point problems. We will argue that the mapping properties of the coefficient operators suggest that block diagonal preconditioners are natural choices for these systems. To illustrate our approach a number of examples will be considered. In particular, parameter‐dependent systems arising in areas like incompressible flow, linear elasticity, and optimal control theory will be studied. The paper contains analysis of several models which have previously been discussed in the literature. However, here each example is discussed with reference to a more unified abstract approach. Copyright © 2010 John Wiley & Sons, Ltd.     

Unified analysis of preconditioning methods for saddle point matrices

Short and unified proofs of spectral properties of major preconditioners for saddle point problems are presented. The need to sufficiently accurately construct approximations of the pivot block and Schur complement matrices to obtain real eigenvalues or eigenvalues with positive real parts and non‐dominating imaginary parts are pointed out. The use of augmented Lagrangian methods for more ill‐conditioned problems are discussed. Copyright © 2014 John Wiley & Sons, Ltd.     

On constraint preconditioners for generalized saddle point matrices

For the iterative solution of large sparse generalized saddle point problems, a class of new constraint preconditioners is presented, and the spectral properties and parameter choices are discussed. Numerical experiments are used to demonstrate the feasibility and effectiveness of the new preconditioners, as well as their advantages over the modified product-type skew-Hermitian triangular splitting (MPSTS) preconditioners.     

Analysis of iterative methods for saddle point problems: a unified approach

In this paper two classes of iterative methods for saddle point problems are considered: inexact Uzawa algorithms and a class of methods with symmetric preconditioners. In both cases the iteration matrix can be transformed to a symmetric matrix by block diagonal matrices, a simple but essential observation which allows one to estimate the convergence rate of both classes by studying associated eigenvalue problems. The obtained estimates apply for a wider range of situations and are partially sharper than the known estimates in literature. A few numerical tests are given which confirm the sharpness of the estimates.

     

A general approach to analyse preconditioners for two‐by‐two block matrices

Two‐by‐two block matrices arise in various applications, such as in domain decomposition methods or when solving boundary value problems discretised by finite elements from the separation of the node set of the mesh into ‘fine’ and ‘coarse’ nodes. Matrices with such a structure, in saddle point form arise also in mixed variable finite element methods and in constrained optimisation problems. A general algebraic approach to construct, analyse and control the accuracy of preconditioners for matrices in two‐by‐two block form is presented. This includes both symmetric and nonsymmetric matrices, as well as indefinite matrices. The action of the preconditioners can involve element‐by‐element approximations and/or geometric or algebraic multigrid/multilevel methods. Copyright © 2011 John Wiley & Sons, Ltd.