A generalization of the HSS-based sequential two-stage method for solving non-Hermitian saddle point problems

For non-Hermitian saddle point problems with non-Hermitian positive definite (1,1)-block, Zhu et al. studied the HSS-based sequential two-stage method (see Zhu et al. Appl. Math. Comput. 242, 907–916 19). However, this approach may not work when the (1,1)-block of the saddle point problems is weakly Hermitian or skew-Hermitian dominant. By introducing a new preconditioning matrix, a generalization of the HSS-based sequential two-stage method is proposed for solving non-Hermitian saddle-point problems with non-Hermitian positive definite and Hermitian or skew-Hermitian dominant (1,1)-block. Theoretical analysis shows that the proposed iterative method is convergent. Numerical experiments are provided to confirm the theoretical results, which demonstrate that the generalized method is effective and feasible for solving saddle point problems with non-Hermitian positive definite and Hermitian or skew-Hermitian dominant (1,1)-block.     

Regularized DPSS Preconditioners for Singular Saddle Point Problems

Recently, Cao proposed a regularized deteriorated positive and skew-Hermitian splitting (RDPSS) preconditioner for the non-Hermitian nonsingular saddle point problem. In this paper, we consider applying RDPSS preconditioner to solve the singular saddle point problem. Moreover, we propose a two-parameter accelerated variant of the RDPSS (ARDPSS) preconditioner to further improve its efficiency. Theoretical analysis proves that the RDPSS and ARDPSS methods are semi-convergent unconditionally. Some spectral properties of the corresponding preconditioned matrices are analyzed. Numerical experiments indicate that better performance can be achieved when applying the ARDPSS preconditioner to accelerate the GMRES method for solving the singular saddle point problem.     

A generalized modified SOR-like method for the singular saddle point problems

Recently, Guo et al. proposed a modified SOR-like (MSOR-like) iteration method for solving the nonsingular saddle point problem. In this paper, we further prove the semi-convergence of this method when it is applied to solve the singular saddle point problems under suitable conditions on the involved iteration parameters. Moreover, the optimal iteration parameters and the corresponding optimal semi-convergence factor for the MSOR-like method are determined. In addition, numerical experiments are used to show the feasibility and effectiveness of the MSOR-like method for solving singular saddle point problems, arising from the incompressible flow problems.     

广义鞍点问题基于PSS的约束预条件子

对于(1,1)块为非Hermitian阵的广义鞍点问题,本文给出了一种基于正定和反对称分裂(Positive definite andskew-Hermitian splitting, PSS)的约束预条件子.该预条件子的(1,1)块由求解非Hermitian正定线性方程组时的PSS迭代法所构造得到.文中分析了PSS约束预条件子的一些性质并证明了预处理迭代法的收敛性.最后用数值算例验证了该预条件子的有效性.     

Preconditioning of GMRES by skew-Hermitian iterations

A class of preconditioners for solving non-Hermitian positive definite systems of linear algebraic equations is proposed and investigated. It is based on Hermitian and skew-Hermitian splitting of the initial matrix. A generalization for saddle point systems having semidefinite or singular (1, 1) blocks is given. Our approach is based on an augmented Lagrangian formulation. It is shown that such preconditioners can be efficiently used for the iterative solution of systems of linear algebraic equations by the GMRES method.     

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.     

关于广义鞍点问题的HSS迭代方法的收缩因子(英文)

白中治等提出了解非埃尔米特正定线性方程组的埃尔米特和反埃尔米特分裂(HSS)迭代方法(Bai Z Z,Golub G H,Ng M K.Hermitian and skew-Hermitian splitting methodsfor non-Hermitian positive definite linear systems.SIAM J.Matrix Anal.Appl.,2003,24:603-626).本文精确地估计了用HSS迭代方法求解广义鞍点问题时在加权2-范数和2-范数下的收缩因子.在实际的计算中,正是这些收缩因子而不是迭代矩阵的谱半径,本质上控制着HSS迭代方法的实际收敛速度.根据文中的分析,求解广义鞍点问题的HSS迭代方法的收缩因子在加权2-范数下等于1,在2-范数下它会大于等于1,而在某种适当选取的范数之下,它则会小于1.最后,用数值算例说明了理论结果的正确性.     

Semi-convergence analysis of preconditioned deteriorated PSS iteration method for singular saddle point problems

In this paper, we propose a two-parameter preconditioned variant of the deteriorated PSS iteration method (J. Comput. Appl. Math., 273, 41–60 (2015)) for solving singular saddle point problems. Semi-convergence analysis shows that the new iteration method is convergent unconditionally. The new iteration method can also be regarded as a preconditioner to accelerate the convergence of Krylov subspace methods. Eigenvalue distribution of the corresponding preconditioned matrix is presented, which is instructive for the Krylov subspace acceleration. Note that, when the leading block of the saddle point matrix is symmetric, the new iteration method will reduce to the preconditioned accelerated HSS iteration method (Numer. Algor., 63 (3), 521–535 2013), the semi-convergence conditions of which can be simplified by the results in this paper. To further improve the effectiveness of the new iteration method, a relaxed variant is given, which has much better convergence and spectral properties. Numerical experiments are presented to investigate the performance of the new iteration methods for solving singular saddle point problems.     

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.     

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.

     

鞍点问题的广义位移分裂预条件子

对于大型稀疏非Hermitian正定线性方程组,Bai等人提出了一种位移分裂预条件子(J.Comput.Math.,24(2006)539-552).本文将这种思想用到鞍点问题上并提出了一种广义位移分裂(Generalized Shift Splitting,GSS)预条件子,同时证明了该预条件子所对应分裂迭代法的无条件收敛性.最后用数值算例验证了新预条件子的有效性.     

Preconditioned AHSS iteration method for singular saddle point problems

In this paper, for solving the singular saddle point problems, we present a new preconditioned accelerated Hermitian and skew-Hermitian splitting (AHSS) iteration method. The semi-convergence of this method and the eigenvalue distribution of the preconditioned iteration matrix are studied. In addition, we prove that all eigenvalues of the iteration matrix are clustered for any positive iteration parameters α and β. Numerical experiments illustrate the theoretical results and examine the numerical effectiveness of the AHSS iteration method served either as a preconditioner or as a solver.     

A relaxed positive semi-definite and skew-Hermitian splitting preconditioner for non-Hermitian generalized saddle point problems

For non-Hermitian saddle point linear systems, Pan, Ng and Bai presented a positive semi-definite and skew-Hermitian splitting (PSS) preconditioner (Pan et al. Appl. Math. Comput. 172, 762–771 2006), to accelerate the convergence rate of the Krylov subspace iteration methods like the GMRES method. In this paper, a relaxed positive semi-definite and skew-Hermitian (RPSS) splitting preconditioner based on the PSS preconditioner for the non-Hermitian generalized saddle point problems is considered. The distribution of eigenvalues and the form of the eigenvectors of the preconditioned matrix are analyzed. Moreover, an upper bound on the degree of the minimal polynomial is also studied. Finally, numerical experiments of a model Navier-Stokes equation are presented to illustrate the efficiency of the RPSS preconditioner compared to the PSS preconditioner, the block diagonal preconditioner (BD), and the block triangular preconditioner (BT) in terms of the number of iteration and computational time.     

Projected Schur complement method for solving non‐symmetric systems arising from a smooth fictitious domain approach

This paper deals with a fast method for solving large‐scale algebraic saddle‐point systems arising from fictitious domain formulations of elliptic boundary value problems. A new variant of the fictitious domain approach is analyzed. Boundary conditions are enforced by control variables introduced on an auxiliary boundary located outside the original domain. This approach has a significantly higher convergence rate; however, the algebraic systems resulting from finite element discretizations are typically non‐symmetric. The presented method is based on the Schur complement reduction. If the stiffness matrix is singular, the reduced system can be formulated again as another saddle‐point problem. Its modification by orthogonal projectors leads to an equation that can be efficiently solved using a projected Krylov subspace method for non‐symmetric operators. For this purpose, the projected variant of the BiCGSTAB algorithm is derived from the non‐projected one. The behavior of the method is illustrated by examples, in which the BiCGSTAB iterations are accelerated by a multigrid strategy. Copyright © 2007 John Wiley & Sons, Ltd.     

On generalized stationary iterative method for solving the saddle point problems

In this paper, the generalized stationary iterative (GSI) method is studied for solving the saddle point problems. The convergence of this method is studied under suitable restrictions on iteration parameters. Numerical example for solving Stokes equation is presented to show the superiority of GSI method.     

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.     

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.     

On local Hermitian and skew-Hermitian splitting iteration methods for generalized saddle point problems

In this paper, we first present a local Hermitian and skew-Hermitian splitting (LHSS) iteration method for solving a class of generalized saddle point problems. The new method converges to the solution under suitable restrictions on the preconditioning matrix. Then we give a modified LHSS (MLHSS) iteration method, and further extend it to the generalized saddle point problems, obtaining the so-called generalized MLHSS (GMLHSS) iteration method. Numerical experiments for a model Navier-Stokes problem are given, and the results show that the new methods outperform the classical Uzawa method and the inexact parameterized Uzawa method.     

On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling

Recently, Freund and Nachtigal proposed the quasi-minimal residual algorithm (QMR) for solving general nonsingular non-Hermitian linear systems. The method is based on the Lanczos process, and thus it involves matrix—vector products with both the coefficient matrix of the linear system and its transpose. Freund developed a variant of QMR, the transpose-free QMR algorithm (TFQMR), that only requires products with the coefficient matrix. In this paper, the use of QMR and TFQMR for solving singular systems is explored. First, a convergence result for the general class of Krylov-subspace methods applied to singular systems is presented. Then, it is shown that QMR and TFQMR both converge for consistent singular linear systems with coefficient matrices of index 1. Singular systems of this type arise in Markov chain modeling. For this particular application, numerical experiments are reported.     

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.