Efficient Algorithm For Solving Three Kinds Of Saddle Point Problems

The saddle point problems arise extensively in the fields of scientific computing and engineering applications,including computational fluid dynamics,optimization,optimal control,constrained and weighted least squares estimation.As a special type of linear systems,the coefficient,matrices of the saddle point problems are large and sparse.Then the iterative methods are often used to solve saddle point problems since the direct solver requires a great deal of memory space and longer operation time.However,the iterative method often lacks stability and converges very slowly even not converges for some practical problems when use it directly.Therefore,it is necessary to improve the spectral properties of the coefficient matrices by means of suitable preconditioners to make the iterative methods have rapidly convergence properties and higher computational efficiency.Many iterative methods have been developed to solve the saddle point problems by making use of the algebraic properties and the sparse structure of the coefficient matrices.However,there is no way to solve all kinds of saddle point problems due to the indefinite and poor spectrum properties of their coefficient matrices.Thus,it is of great significance to construct the efficient and stable numerical methods according to the properties of the saddle point problems and practical problems.This paper mainly studies the iterative solutions for three main types saddle point problems.Some iterative methods and preconditioners are designed and constructed for saddle point problems,generalized nonsymmetric saddle point problems and general block two-by-two linear systems drawing lessons from the existing classical methods,and considering the factors of algorithm realization,convergence rate,spectral properties and so on.The main works and innovations are as follows:1.the Uzawa splitting(US)iteration method is first,generalized to obtain a block-diagonally preconditioned Uzawa splitting(BDP-US)method for solving the saddle-point problems,and a sufficient condition is provided to ensure the convergence of BDP-US method.Based on this method,a preconditioner is presented and the spectral properties of the preconditioned matrix are also analyzed.Meanwhile,the choice for the parameters of this method is discussed.Numerical results are provided to support the validity of the theoretical results,and demonstrate the effectiveness of BDP-US method and corresponding splitting preconditioner.Then,a new parameter setting is presented for the MPAHSS-parameterized Uzawa(MPAHSS-PU)method based on the modified preconditioned accelerated Hermitian and skew-Hermitian splitting(MPAHSS)and triangular splitting iterative methods.A sufficient condition is provided to ensure the convergence of MPAHSS-PU method with the new parameter setting,and the choice of its parameters is discussed.The new parameter setting not only lessens the limitation on parameters,but also overcomes the drawbacks of the MPAHSS-PU method.The validity of the theoretical results and the performance of MPAHSS-PU method with the new parameter setting are demonstrated by numerical examples.2.Inspired by the idea of the parameterized shift-splitting(PSS),a modified PSS(MPSS)preconditioner is presented for the generalized nonsymmetric saddle point problems.All eigenvalues of the corresponding preconditioned matrix are proved to be clustered around 1,and the unconditional convergence of the MPSS iteration method is shown under certain conditions.The proposed method overcomes the shortfalls of the PSS iteration method.Numerical experiments are provided to validate the theoretical results and illustrate the effectiveness of the proposed preconditioner.3.Based on the generalized the parameterized inexact Uzawa iteration method 2 and the parameterized preconditioned technique,we first construct a two-parameter triangular splitting preconditioner for the general block two-by-two linear systems.Then,a matrix splitting preconditioner is obtained by extending the matrix splitting preconditioner proposed for solving the generalized saddle point problem.All eigenvalues of these two corresponding preconditioned matrices are proved to cluster around 0 or 1 by analyzing their spectral properties in detail.Numerical results are provided to support the validity of the theoretical results,and demonstrate the effectiveness of these two preconditioners by making a comparison of them with the classical block-diagonal and block-triangular preconditioners applied to the generalized minimal residual(GMRES)method.