Shift-splitting preconditioners for a class of block three-by-three saddle point problems

In this paper, shift-splitting preconditioners are studied for a special class of block three-by-three saddle point problems, which arise from many practical problems and are different from the traditional saddle point problems. It is proved that the block three-by-three saddle point matrix is positive stable and the corresponding shift-splitting stationary iteration method is unconditionally convergent, which leads to a nice clustering property of the eigenvalues of the shift-splitting preconditioned matrix. Numerical results show that the proposed shift-splitting preconditioners outperform much better than some existing block diagonal preconditioners studied recently.     

A parameterized extended shift-splitting preconditioner for nonsymmetric saddle point problems

In this article, a parameterized extended shift-splitting (PESS) method and its induced preconditioner are given for solving nonsingular and nonsymmetric saddle point problems with nonsymmetric positive definite (1,1) part. The convergence analysis of the $PESS$ iteration method is discussed. The distribution of eigenvalues of the preconditioned matrix is provided. A number of experiments are given to verify the efficiency of the $PESS$ method for solving nonsymmetric saddle-point problems.     

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.     

A note on constraint preconditioners for nonsymmetric saddle point problems

A class of constraint preconditioners for solving two‐by‐two block linear equations with the (1,2)‐block being the transpose of the (2,1)‐block and the (2,2)‐block being zero was investigated in a recent paper of Cao (Numer. Math. 2006; 103 :47–61). In this short note, we extend his idea by allowing the (1,2)‐block to be not equal to the transpose of the (2,1)‐block. Results concerning the spectrum, the form of the eigenvectors and the convergence behaviour of a Krylov subspace method, such as GMRES are presented. Copyright © 2007 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.     

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.     

Spectral properties of primal-based penalty preconditioners for saddle point problems

For large and sparse saddle point linear systems, this paper gives further spectral properties of the primal-based penalty preconditioners introduced in [C.R. Dohrmann, R.B. Lehoucq, A primal-based penalty preconditioner for elliptic saddle point systems, SIAM J. Numer. Anal. 44 (2006) 270-282]. The regions containing the real and non-real eigenvalues of the preconditioned matrix are obtained. The model of the Stokes problem is supplemented to illustrate the theoretical results and to test the quality of the primal-based penalty preconditioner.     

A class of constraint preconditioners for nonsymmetric saddle point matrices

We consider the use of a class of constraint preconditioners for the application of the Krylov subspace iterative method to the solution of large nonsymmetric, indefinite linear systems. The eigensolution distribution of the preconditioned matrix is determined and the convergence behavior of a Krylov subspace method such as GMRES is described. The choices of the parameter matrices and the implementation of the preconditioning step are discussed. Numerical experiments are presented. This work is supported by NSFC Projects 10171021 and 10471027.     

Uzawa type algorithms for nonsymmetric saddle point problems

In this paper, we consider iterative algorithms of Uzawa type for solving linear nonsymmetric saddle point problems. Specifically, we consider systems, written as usual in block form, where the upper left block is an invertible linear operator with positive definite symmetric part. Such saddle point problems arise, for example, in certain finite element and finite difference discretizations of Navier-Stokes equations, Oseen equations, and mixed finite element discretization of second order convection-diffusion problems. We consider two algorithms, each of which utilizes a preconditioner for the operator in the upper left block. Convergence results for the algorithms are established in appropriate norms. The convergence of one of the algorithms is shown assuming only that the preconditioner is spectrally equivalent to the inverse of the symmetric part of the operator. The other algorithm is shown to converge provided that the preconditioner is a sufficiently accurate approximation of the inverse of the upper left block. Applications to the solution of steady-state Navier-Stokes equations are discussed, and, finally, the results of numerical experiments involving the algorithms are presented.

     

A generalization of parameterized inexact Uzawa method for generalized saddle point problems

Recently, a class of parameterized inexact Uzawa methods has been proposed for generalized saddle point problems by Bai and Wang [Z.-Z. Bai, Z.-Q. Wang, On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl. 428 (2008) 2900–2932], and a generalization of the inexact parameterized Uzawa method has been studied for augmented linear systems by Chen and Jiang [F. Chen, Y.-L. Jiang, A generalization of the inexact parameterized Uzawa methods for saddle point problems, Appl. Math. Comput. (2008)]. This paper is concerned about a generalization of the parameterized inexact Uzawa method for solving the generalized saddle point problems with nonzero (2, 2) blocks. Some new iterative methods are presented and their convergence are studied in depth. By choosing different parameter matrices, we derive a series of existing and new iterative methods, including the preconditioned Uzawa method, the inexact Uzawa method, the SOR-like method, the GSOR method, the GIAOR method, the PIU method, the APIU method and so on. Numerical experiments are used to demonstrate the feasibility and effectiveness of the generalized parameterized inexact Uzawa methods.     

An alternating preconditioner for saddle point problems

Based on matrix splittings, a new alternating preconditioner with two parameters is proposed for solving saddle point problems. Some theoretical analyses for the eigenvalues of the associated preconditioned matrix are given. The choice of the parameters is considered and the quasi-optimal parameters are obtained. The new preconditioner with these quasi-optimal parameters significantly improves the convergence rate of the generalized minimal residual (GMRES) iteration. Numerical experiments from the linearized Navier-Stokes equations demonstrate the efficiency of the new preconditioner, especially on the larger viscosity parameter ν. Further extensions of the preconditioner to generalized saddle point matrices are also checked.     

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.     

鞍点问题的修正对称超松弛迭代算法

为了提高求解鞍点问题的迭代算法的速度,通过设置合适的加速变量,对修正超松弛迭代算法（简记作MSOR-like算法）和广义对称超松弛迭代算法（简记作GSSOR-like算法）进行了修正,给出了修正对称超松弛迭代算法,即MSSOR-like （modified symmetric successiveover-relaxation）算法,并研究了该算法收敛的充分必要条件.最后,通过数值例子表明,选择合适的参数后,新算法的迭代速度和迭代次数均优于MSOR-like （modified successive overrelaxation）和GSSOR-like （generalized symmetric successive over-relaxation）算法,因此,它是一种较好的解决鞍点问题的算法.     

Block triangular preconditioners for nonsymmetric saddle point problems: field-of-values analysis

A preconditioned minimal residual method for nonsymmetric saddle point problems is analyzed. The proposed preconditioner is of block triangular form. The aim of this article is to show that a rigorous convergence analysis can be performed by using the field of values of the preconditioned linear system. As an example, a saddle point problem obtained from a mixed finite element discretization of the Oseen equations is considered. The convergence estimates obtained by using a field–of–values analysis are independent of the discretization parameter h. Several computational experiments supplement the theoretical results and illustrate the performance of the method. Received March 20, 1997 / Revised version received January 14, 1998     

A splitting preconditioner for saddle point problems

For large sparse systems of linear equations iterative techniques are attractive. In this paper, we study a splitting method for an important class of symmetric and indefinite system. Theoretical analyses show that this method converges to the unique solution of the system of linear equations for all t>0 (t is the parameter). Moreover, all the eigenvalues of the iteration matrix are real and nonnegative and the spectral radius of the iteration matrix is decreasing with respect to the parameter t. Besides, a preconditioning strategy based on the splitting of the symmetric and indefinite coefficient matrices is proposed. The eigensolution of the preconditioned matrix is described and an upper bound of the degree of the minimal polynomials for the preconditioned matrix is obtained. Numerical experiments of a model Stokes problem and a least‐squares problem with linear constraints presented to illustrate the effectiveness of the method. Copyright © 2011 John Wiley & Sons, Ltd.     

Uniform preconditioners for a parameter dependent saddle point problem with application to generalized Stokes interface equations

We consider an abstract parameter dependent saddle-point problem and present a general framework for analyzing robust Schur complement preconditioners. The abstract analysis is applied to a generalized Stokes problem, which yields robustness of the Cahouet-Chabard preconditioner. Motivated by models for two-phase incompressible flows we consider a generalized Stokes interface problem. Application of the general theory results in a new Schur complement preconditioner for this class of problems. The robustness of this preconditioner with respect to several parameters is treated. Results of numerical experiments are given that illustrate robustness properties of the preconditioner.     

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 note on spectrum distribution of constraint preconditioned generalized saddle point matrices

In this note, results concerning the eigenvalue distribution and form of the eigenvectors of the constraint preconditioned generalized saddle point matrix and its minimal polynomial are given. These results extend previous ones that appeared in the literature. Copyright © 2009 John Wiley & Sons, Ltd.     

The corrected Uzawa method for solving saddle point problems

In this paper, we consider the solution of linear systems of saddle point type by correcting the Uzawa algorithm, which has been proposed in [K. Arrow, L. Hurwicz, H. Uzawa, Studies in nonlinear programming, Stanford University Press, Stanford, CA, 1958]. We call this method as corrected Uzawa (CU) method. The convergence of the CU method is analyzed for solving nonsingular saddle point problem as well as the semi‐convergence for the singular case. First, the corrected model for the Uzawa algorithm is established, and the CU algorithm is presented. Then we study the geometric meaning of the CU model. Moreover, we introduce the overall reduction coefficient α to measure the effect of the CU process. It is shown that the CU method converges faster than the Uzawa method and several other methods if the overall reduction coefficient α satisfies certain conditions. Numerical experiments are presented to illustrate the theoretical results and examine the numerical effectiveness of the CU method. Copyright © 2015 John Wiley & Sons, Ltd.     

Local saddle point and a class of convexification methods for nonconvex optimization problems

A class of general transformation methods are proposed to convert a nonconvex optimization problem to another equivalent problem. It is shown that under certain assumptions the existence of a local saddle point or local convexity of the Lagrangian function of the equivalent problem (EP) can be guaranteed. Numerical experiments are given to demonstrate the main results geometrically.