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.     

The alternating-direction iterative method for saddle point problems

In the paper, a new alternating-direction iterative method is proposed based on matrix splittings for solving saddle point problems. The convergence analysis for the new method is given. When the better values of parameters are employed, the proposed method has faster convergence rate and less time cost than the Uzawa algorithm with the optimal parameter and the Hermitian and skew-Hermitian splitting iterative method. Numerical examples further show the effectiveness of the method.     

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.     

On the optimal parameters of GMSSOR method for saddle point problems

For solving saddle point problems, SOR-type methods are investigated by many researchers in the literature. In this short note, we study the GMSSOR method for solving saddle point problems and obtain the optimal parameters which minimize the spectral (or pseudo-spectral) radii of the iteration matrices.     

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.     

PAHSS-PTS alternating splitting iterative methods for nonsingular saddle point problems

In this paper, we propose the PAHSS-PTS alternating splitting iterative methods for nonsingular saddle point problems. Convergence properties of the proposed methods are studied and corresponding convergence results are given under some suitable conditions. Numerical experiments are presented to confirm the theoretical results, which impliy that PAHSS-PTS iterative methods are effective and feasible.     

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

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

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 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.     

Convergence analysis of the corrected Uzawa algorithmfor symmetric saddle point problems简

For the large sparse saddle point problems, Pan and Li recently proposed in [H. K. Pan, W. Li, Math. Numer. Sinica, 2009, 31（3）： 231-242] a corrected Uzawa algorithm based on a nonlinear Uzawa algorithm with two nonlinear approximate inverses, and gave the detailed convergence analysis. In this paper, we focus on the convergence analysis of this corrected Uzawa algorithm, some inaccuracies in [H. K. Pan, W. Li, Math. Numer. Sinica, 2009, 31（3）： 231-242] are pointed out, and a corrected convergence theorem is presented. A special case of this modified Uzawa algorithm is also discussed.     

A generalized preconditioned HSS method for singular saddle point problems

Li et al. recently studied the generalized HSS (GHSS) method for solving singular linear systems (see Li et al., J. Comput. Appl. Math. 236, 2338–2353 (2012)). In this paper, we generalize the method and present a generalized preconditioned Hermitian and skew-Hermitian splitting method (GPHSS) to solve singular saddle point problems. We prove the semi-convergence of GPHSS under some conditions, and weaken some semi-convergent conditions of GHSS, moreover, we analyze the spectral properties of the corresponding preconditioned matrix. Numerical experiments are given to illustrate the efficiency of GPHSS method with appropriate parameters both as a solver and as a preconditioner.     

Extragradient and extrapolation methods with generalized Bregman distances for saddle point problems

In this paper, we introduce two Bregman-type algorithmic frameworks to generalize the extragradient and extrapolation methods. With the help of relative Lipschitzness and the Bregman distance tool, the iteration properties of the proposed frameworks are analyzed. As applied to smooth convex-concave saddle point problems, our theory rediscovers the main results in Mokhtari et al. (2020) [14] for wider frameworks under weaker assumptions via a conceptually different approach.     

Eigenvalue estimates for preconditioned saddle point matrices

New accurate eigenvalue bounds for symmetric matrices of saddle point form are derived and applied for both unpreconditioned and preconditioned versions of the matrices. The estimates enable a better understanding of how preconditioners should be chosen. The preconditioners provide efficient iterative solution of the corresponding linear systems with, for some important applications, an optimal order of computational complexity. The methods are applied for Stokes problem and for linear elasticity problems. Copyright © 2005 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.     

Semi-convergence analysis of the Uzawa-SOR methods for singular saddle point problems

Recently, Zhang and Shang proposed a class of Uzawa-SOR methods for solving the nonsingular saddle point problems; see Zhang and Shang (2010). In this paper, we give the semi-convergence analysis of this method when it is applied to solve the singular saddle point problems under some conditions. Finally, numerical experiments are presented to illustrate the feasibility and effectiveness of this method.     

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.     

Large-scale semidefinite programming via a saddle point Mirror-Prox algorithm

In this paper, we first demonstrate that positive semidefiniteness of a large well-structured sparse symmetric matrix can be represented via positive semidefiniteness of a bunch of smaller matrices linked, in a linear fashion, to the matrix. We derive also the “dual counterpart” of the outlined representation, which expresses the possibility of positive semidefinite completion of a well-structured partially defined symmetric matrix in terms of positive semidefiniteness of a specific bunch of fully defined submatrices of the matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex–concave saddle point problems, which can be solved by a Prox-method developed in [6] with efficiency . Implementations and some numerical results for large-scale Lovász capacity and MAXCUT problems are finally presented.      

On the eigenvalue distribution of preconditioned nonsymmetric saddle point matrices

In this paper, we derive bounds for the complex eigenvalues of a nonsymmetric saddle point matrix with a symmetric positive semidefinite (2,2) block, that extend the corresponding previous bounds obtained by Bergamaschi. For the nonsymmetric saddle point problem, we propose a block diagonal preconditioner for the conjugate gradient method in a nonstandard inner product. Numerical experiments are also included to test the performance of the presented preconditioner. Copyright © 2013 John Wiley & Sons, Ltd.     

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.

     

Constrained extremum problems with infinite dimensional image. Selection and saddle point

The paper deals with Image Space Analysis for constrained extremum problems having infinite dimensional image. It is shown that the introduction of selection for point- to-set maps and of quasi-multipliers allows one to establish sufficient optimality conditions for problems, where the classic ones fail.