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

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.     

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.     

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.     

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.     

On eigenvalue distribution of constraint‐preconditioned symmetric saddle point matrices

This paper is devoted to the analysis of the eigenvalue distribution of two classes of block preconditioners for the generalized saddle point problem. Most of the bounds developed improve those appeared in previously published works. Numerical results onto a realistic test problem give evidence of the effectiveness of the estimates on the spectrum of preconditioned matrices. Copyright © 2011 John Wiley & Sons, Ltd.     

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.     

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.     

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

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

Uzawa methods for 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 some other applications. The direct extension of the Uzawa method for solving this block three‐by‐three saddle‐point problem requires the exact solution of a symmetric indefinite system of linear equations at each step. To avoid heavy computations at each step, we propose an inexact Uzawa method, which solves the symmetric indefinite linear system in some inexact way. Under suitable assumptions, we show that the inexact Uzawa method converges to the unique solution of the saddle‐point problem within the approximation level. Two special algorithms are customized for the inexact Uzawa method combining the splitting iteration method and a preconditioning technique, respectively. Numerical experiments are presented, which demonstrated the usefulness of the inexact Uzawa method and the two customized algorithms.     

Combination preconditioning of saddle point systems for positive definiteness

Amongst recent contributions to preconditioning methods for saddle point systems, standard iterative methods in nonstandard inner products have been usefully employed. Krzy?anowski (Numerical Linear Algebra with Applications 2011; 18 :123–140) identified a two‐parameter family of preconditioners in this context and Stoll and Wathen (SIAM Journal on Matrix Analysis and Applications 2008; 30 :582–608) introduced combination preconditioning, where two preconditioners, self‐adjoint with respect to different inner products, can lead to further preconditioners and associated bilinear forms or inner products. Preconditioners that render the preconditioned saddle point matrix nonsymmetric but self‐adjoint with respect to a nonstandard inner product always allow a MINRES‐type method (‐PMINRES) to be applied in the relevant inner product. If the preconditioned matrix is also positive definite with respect to the inner product, a more efficient CG‐like method (‐PCG) can be reliably used. We establish eigenvalue expressions for Krzy?anowski preconditioners and show that for a specific choice of parameters, although the Krzy?anowski preconditioned saddle point matrix is self‐adjoint with respect to an inner product, it is never positive definite. We provide explicit expressions for the combination of certain preconditioners and prove the rather counterintuitive result that the combination of two specific preconditioners for which only ‐PMINRES can be reliably used leads to a preconditioner for which, for certain parameter choices, ‐PCG is reliably applicable. That is, combining two indefinite preconditioners can lead to a positive definite preconditioner. This combination preconditioner outperforms either of the two preconditioners from which it is formed for a number of test problems. Copyright © 2012 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.     

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.     

An iterative method based on a modified Lagrangian functional for finding a saddle point in the semicoercive Signorini problem

The iterative Uzawa method with a modified Lagrangian functional is examined in the framework of the Signorini problem.     

A preconditioner for generalized saddle point problems: Application to 3D stationary Navier‐Stokes equations

In this article we consider the stationary Navier‐Stokes system discretized by finite element methods which do not satisfy the inf‐sup condition. These discretizations typically take the form of a variational problem with stabilization terms. Such a problem may be transformed by iteration methods into a sequence of linear, Oseen‐type variational problems. On the algebraic level, these problems belong to a certain class of linear systems with nonsymmetric system matrices (“generalized saddle point problems”). We show that if the underlying finite element spaces satisfy a generalized inf‐sup condition, these problems have a unique solution. Moreover, we introduce a block triangular preconditioner and we show how the eigenvalue bounds of the preconditioned system matrix depend on the coercivity constant and continuity bounds of the bilinear forms arising in the variational problem. Finally we prove that the stabilized P1‐P1 finite element method proposed by Rebollo is covered by our theory and we show that the condition number of the preconditioned system matrix is independent of the mesh size. Numerical tests with 3D stationary Navier‐Stokes flows confirm our results. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

Modified block preconditioner for generalized saddle point matrices with highly singular(1,1) blocks

ABSTRACT

In this paper, based on the preconditioners presented by Zhang [A new preconditioner for generalized saddle matrices with highly singular(1,1) blocks. Int J Comput Maths. 2014;91(9):2091-2101], we consider a modified block preconditioner for generalized saddle point matrices whose coefficient matrices have singular (1,1) blocks. Moreover, theoretical analysis gives the eigenvalue distribution, forms of the eigenvectors and the minimal polynomial. Finally, numerical examples show the eigenvalue distribution with the presented preconditioner and confirm our analysis.     

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.     

A note on block preconditioner for generalized saddle point matrices with highly singular (1,1) block

In this paper, we present a block triangular preconditioner for generalized saddle point matrices whose coefficient matrices have singular (1,1) blocks. Theoretical analysis shows that all the eigenvalues of the preconditioned matrix are strongly clustered when choosing an optimal parameter. Numerical experiments are given to demonstrate the efficiency of the presented preconditioner.