Convergence analysis of the corrected Uzawa algorithm for 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 New Choice of the Preconditioner of PHSS Method for Saddle Point Problems

Bai, Golub and Pan presented a preconditioned Hermitian and skew-Hermitian splitting(PHSS) method [Numerische Mathematik, 2004, 32: 1-32] for non-Hermitian positive semidefinite linear systems. We improve the method to solve saddle point systems whose(1,1) block is a symmetric positive definite M-matrix with a new choice of the preconditioner and compare it with other preconditioners. The results show that the new preconditioner outperforms the previous ones.

A Note on Parameterized Preconditioned Method for Singular Saddle Point Problems

Recently, some authors (Li, Yang and Wu, 2014) studied the parameterized preconditioned HSS (PPHSS) method for solving saddle point problems. In this short note, we further discuss the PPHSS method for solving singular saddle point problems. We prove the semi-convergence of the PPHSS method under some conditions. Numerical experiments are given to illustrate the efficiency of the method with appropriate parameters.

PRECONDITIONED HSS-LIKE ITERATIVE METHOD FOR SADDLE POINT PROBLEMS

A new HSS-like iterative method is first proposed based on HSS-like splitting of non- Hermitian （1,1） block for solving saddle point problems. The convergence analysis for the new method is given. Meanwhile, we consider the solution of saddle point systems by preconditioned Krylov subspaee method and discuss some spectral properties of the preconditioned saddle point matrices. Numerical experiments are given to validate the performances of the preconditioners.

Convergence of a Class of Stationary Iterative Methods for Saddle Point Problems

A unified convergence theory is derived for a class of stationary iterative methods for solving linear equality constrained quadratic programs or saddle point problems.This class is constructed from essentially all possible splittings of the submatrix residing in the(1,1)-block of the augmented saddle point matrix that would produce non-expansive iterations.The classic augmented Lagrangian method and alternating direction method of multipliers are two special members of this class.

A MODIFIED PRECONDITIONER FOR PARAMETERIZED INEXACT UZAWA METHOD FOR INDEFINITE SADDLE POINT PROBLEMS

The preconditioner for parameterized inexact Uzawa methods have been used to solve some indefinite saddle point problems. Firstly, we modify the preconditioner by making it more generalized, then we use theoretical analyses to show that the iteration method converges under certain conditions. Moreover, we discuss the optimal parameter and matrices based on these conditions. Finally, we propose two improved methods. Numerical experiments are provided to show the effectiveness of the modified preconditioner. All methods have fantastic convergence rates by choosing the optimal parameter and matrices.

Dynamic System for Solving Saddle Point Problems in Hilbert Spaces and Its Application to Neural Computing

This paper studies the existence and uniqueness of solutions and the stability and convergence of a dynamic system for solving saddle point problems （SPP） in Hilbert spaces. The analysis first converts the SPP into a problem of searching for equilibriums of a dynamic system using a criterion for solutions of the SPP, then shows the existence and uniqueness of the solutions by creating a positive function whose Fréchet derivative is decreasing along any solution. The construction of positively invariant subsets gives the global stability and convergence of this dynamic system, that is, the dynamic system globally converges to some exact solution of the SPP. Finally, the paper also shows that the obtained results can be applied to neural computing for solving SPP.

A new alternating positive semidefinite splitting preconditioner for saddle point problems from time-harmonic eddy current models

Based on the special positive semidefinite splittings of the saddle point matrix, we propose a new Mternating positive semidefinite splitting （APSS） iteration method for the saddle point problem arising from the finite element discretization of the hybrid formulation of the time-harmonic eddy current problem. We prove that the new APSS iteration method is unconditionally convergent for both cases of the simple topology and the general topology. The new APSS matrix can be used as a preconditioner to accelerate the convergence rate of Krylov subspace methods. Numerical results show that the new APSS preconditioner is superior to the existing preconditioners.

A RELAXED HSS PRECONDITIONER FOR SADDLE POINT PROBLEMS FROM MESHFREE DISCRETIZATION＊

In this paper, a relaxed Hermitian and skew-Hermitian splitting （RHSS） preconditioner is proposed for saddle point problems from the element-free Galerkin （EFG） discretization method. The EFG method is one of the most widely used meshfree methods for solving partial differential equations. The RHSS preconditioner is constructed much closer to the coefficient matrix than the well-known HSS preconditioner, resulting in a RHSS fixed-point iteration. Convergence of the RHSS iteration is analyzed and an optimal parameter, which minimizes the spectral radius of the iteration matrix is described. Using the RHSS pre- conditioner to accelerate the convergence of some Krylov subspace methods （like GMRES） is also studied. Theoretical analyses show that the eigenvalues of the RHSS precondi- tioned matrix are real and located in a positive interval. Eigenvector distribution and an upper bound of the degree of the minimal polynomial of the preconditioned matrix are obtained. A practical parameter is suggested in implementing the RHSS preconditioner. Finally, some numerical experiments are illustrated to show the effectiveness of the new preconditioner.

奇异鞍点问题中广义位移分裂迭代方法的半收敛性分析

Recently,some authors(Shen and Shi,2016)studied the generalized shiftsplitting(GSS)iteration method for singular saddle point problem with nonsymmetric positive definite(1,1)-block and symmetric positive semidefinite(2,2)-block.In this paper,we further apply the GSS iteration method to solve singular saddle point problem with nonsymmetric positive semidefinite(1,1)-block and symmetric positive semidefinite(2,2)-block,prove the semi-convergence of the GSS iteration method and analyze the spectral properties of the corresponding preconditioned matrix.Numerical experiment is given to indicate that the GSS iteration method with appropriate iteration parameters is effective and competitive for practical use.

THE GENERALIZED LOCAL HERMITIAN AND SKEW-HERMITIAN SPLITTING ITERATION METHODS FOR THE NON-HERMITIAN GENERALIZED SADDLE POINT PROBLEMS

For large and sparse saddle point problems, Zhu studied a class of generalized local Hermitian and skew-Hermitian splitting iteration methods for non-Hermitian saddle point problem [M.-Z. Zhu, Appl. Math. Comput. 218 （2012） 8816-8824 ]. In this paper, we further investigate the generalized local Hermitian and skew-Hermitian splitting （GLHSS） iteration methods for solving non-Hermitian generalized saddle point problems. With different choices of the parameter matrices, we derive conditions for guaranteeing the con- vergence of these iterative methods. Numerical experiments are presented to illustrate the effectiveness of our GLHSS iteration methods as well as the preconditioners.

Spectral Analysis for HSS Preconditioners

In this paper,we are interested in HSS preconditioners for saddle point lin- ear systems with a nonzero(2,2)-th block.We study an approximation of the spectra of HSS preconditioned matrices and use these results to illustrate and explain the spectra obtained from numerical examples,where the previous spectral analysis of HSS precon- ditioned matrices does not cover.

A NEW PRECONDITIONING STRATEGY FOR SOLVING A CLASS OF TIME-DEPENDENT PDE-CONSTRAINED OPTIMIZATION PROBLEMS

In this paper, by exploiting the special block and sparse structure of the coefficient matrix, we present a new preconditioning strategy for solving large sparse linear systems arising in the time-dependent distributed control problem involving the heat equation with two different functions. First a natural order-reduction is performed, and then the reduced- order linear system of equations is solved by the preconditioned MINRES algorithm with a new preconditioning techniques. The spectral properties of the preconditioned matrix are analyzed. Numerical results demonstrate that the preconditioning strategy for solving the large sparse systems discretized from the time-dependent problems is more effective for a wide range of mesh sizes and the value of the regularization parameter.

An Augmented Lagrangian Deep Learning Method for Variational Problems with Essential Boundary Conditions

This paper is concerned with a novel deep learning method for variational problems with essential boundary conditions.To this end,wefirst reformulate the original problem into a minimax problem corresponding to a feasible augmented La-grangian,which can be solved by the augmented Lagrangian method in an infinite dimensional setting.Based on this,by expressing the primal and dual variables with two individual deep neural network functions,we present an augmented Lagrangian deep learning method for which the parameters are trained by the stochastic optimiza-tion method together with a projection technique.Compared to the traditional penalty method,the new method admits two main advantages:i)the choice of the penalty parameter isflexible and robust,and ii)the numerical solution is more accurate in the same magnitude of computational cost.As typical applications,we apply the new ap-proach to solve elliptic problems and(nonlinear)eigenvalue problems with essential boundary conditions,and numerical experiments are presented to show the effective-ness of the new method.

THE RESTRICTIVELY PRECONDITIONED CONJUGATE GRADIENT METHODS ON NORMAL RESIDUAL FOR BLOCK TWO-BY-TWO LINEAR SYSTEMS

The restrictively preconditioned conjugate gradient （RPCG） method is further developed to solve large sparse system of linear equations of a block two-by-two structure. The basic idea of this new approach is that we apply the RPCG method to the normal-residual equation of the block two-by-two linear system and construct each required approximate matrix by making use of the incomplete orthogonal factorization of the involved matrix blocks. Numerical experiments show that the new method, called the restrictively preconditioned conjugate gradient on normal residual （RPCGNR）, is more robust and effective than either the known RPCG method or the standard conjugate gradient on normal residual （CGNR） method when being used for solving the large sparse saddle point problems.

Efficient Variable-Coefficient Finite-Volume Stokes Solvers

We investigate several robust preconditioners for solving the saddle-point linear systems that arise from spatial discretization of unsteady and steady variablecoefficient Stokes equations on a uniform staggered grid.Building on the success of using the classical projection method as a preconditioner for the coupled velocitypressure system[B.E.Griffith,J.Comp.Phys.,228(2009),pp.7565–7595],as well as established techniques for steady and unsteady Stokes flow in the finite-element literature,we construct preconditioners that employ independent generalized Helmholtz and Poisson solvers for the velocity and pressure subproblems.We demonstrate that only a single cycle of a standard geometric multigrid algorithm serves as an effective inexact solver for each of these subproblems.Contrary to traditional wisdom,we find that the Stokes problem can be solved nearly as efficiently as the independent pressure and velocity subproblems,making the overall cost of solving the Stokes system comparable to the cost of classical projection or fractional step methods for incompressible flow,even for steady flow and in the presence of large density and viscosity contrasts.Two of the five preconditioners considered here are found to be robust to GMRES restarts and to increasing problem size,making them suitable for large-scale problems.Our work opens many possibilities for constructing novel unsplit temporal integrators for finite-volume spatial discretizations of the equations of low Mach and incompressible flow dynamics.

MODIFIED ALTERNATING POSITIVE SEMIDEFINITE SPLITTING PRECONDITIONER FOR TIME-HARMONIC EDDY CURRENT MODELS

In this paper,we consider a modified alternating positive semidefinite splitting preconditioner for solving the saddle point problems arising from the finite element discretization of the hybrid formulation of the time-harmonic eddy current model.The eigenvalue distribution and an upper bound of the degree of the minimal polynomial of the preconditioned matrix are studied for both simple and general topology.Numerical results demonstrate the effectiveness of the proposed preconditioner when it is used to accelerate the convergence rate of Krylov subspace methods such as GMRES.