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

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

On HSS-based constraint preconditioners for generalized saddle-point problems

For the generalized saddle-point problems with non-Hermitian (1,1) blocks, we present an HSS-based constraint preconditioner, in which the (1,1) block of the preconditioner is constructed by the HSS method for solving the non-Hermitian positive definite linear systems. We analyze the invertibility of the HSS-based constraint preconditioner and prove the convergence of the preconditioned iteration method. Numerical experiments are used to demonstrate the efficiency of the preconditioner as well as the corresponding preconditioned iteration method, especially when the (1,1) block of the saddle-point matrix is essentially non-Hermitian.     

Matrix-free interior point method

In this paper we present a redesign of a linear algebra kernel of an interior point method to avoid the explicit use of problem matrices. The only access to the original problem data needed are the matrix-vector multiplications with the Hessian and Jacobian matrices. Such a redesign requires the use of suitably preconditioned iterative methods and imposes restrictions on the way the preconditioner is computed. A two-step approach is used to design a preconditioner. First, the Newton equation system is regularized to guarantee better numerical properties and then it is preconditioned. The preconditioner is implicit, that is, its computation requires only matrix-vector multiplications with the original problem data. The method is therefore well-suited to problems in which matrices are not explicitly available and/or are too large to be stored in computer memory. Numerical properties of the approach are studied including the analysis of the conditioning of the regularized system and that of the preconditioned regularized system. The method has been implemented and preliminary computational results for small problems limited to 1 million of variables and 10 million of nonzero elements demonstrate the feasibility of the approach.     

A generalized variant of the deteriorated PSS preconditioner for nonsymmetric saddle point problems

Based on the variant of the deteriorated positive-definite and skew-Hermitian splitting (VDPSS) preconditioner developed by Zhang and Gu (BIT Numer. Math. 56:587–604, 2016), a generalized VDPSS (GVDPSS) preconditioner is established in this paper by replacing the parameter α in (2,2)-block of the VDPSS preconditioner by another parameter β. This preconditioner can also be viewed as a generalized form of the VDPSS preconditioner and the new relaxed HSS (NRHSS) preconditioner which has been exhibited by Salkuyeh and Masoudi (Numer. Algorithms, 2016). The convergence properties of the GVDPSS iteration method are derived. Meanwhile, the distribution of eigenvalues and the forms of the eigenvectors of the preconditioned matrix are analyzed in detail. We also study the upper bounds on the degree of the minimum polynomial of the preconditioned matrix. Numerical experiments are implemented to illustrate the effectiveness of the GVDPSS preconditioner and verify that the GVDPSS preconditioned generalized minimal residual method is superior to the DPSS, relaxed DPSS, SIMPLE-like, NRHSS, and VDPSS preconditioned ones for solving saddle point problems in terms of the iterations and computational times.     

Preconditioned GMRES methods with incomplete Givens orthogonalization method for large sparse least-squares problems

We propose to precondition the GMRES method by using the incomplete Givens orthogonalization (IGO) method for the solution of large sparse linear least-squares problems. Theoretical analysis shows that the preconditioner satisfies the sufficient condition that can guarantee that the preconditioned GMRES method will never break down and always give the least-squares solution of the original problem. Numerical experiments further confirm that the new preconditioner is efficient. We also find that the IGO preconditioned BA-GMRES method is superior to the corresponding CGLS method for ill-conditioned and singular least-squares problems.     

Regularization and preconditioning of KKT systems arising in nonnegative least‐squares problems

A regularized Newton‐like method for solving nonnegative least‐squares problems is proposed and analysed in this paper. A preconditioner for KKT systems arising in the method is introduced and spectral properties of the preconditioned matrix are analysed. A bound on the condition number of the preconditioned matrix is provided. The bound does not depend on the interior‐point scaling matrix. Preliminary computational results confirm the effectiveness of the preconditioner and fast convergence of the iterative method established by the analysis performed in this paper. Copyright © 2008 John Wiley & Sons, Ltd.     

广义鞍点问题的松弛维数分解预条件子

本文将Benzi等提出的松弛维数分解(Relaxed dimensionalfactorization, RDF)预条件子进一步推广到广义鞍点问题上,并称为GRDF(Generalized RDF)预条件子.该预条件子可看做是用维数分裂迭代法求解广义鞍点问题而导出的改进维数分裂(Modified dimensional split, MDS)预条件子的松弛形式, 它相比MDS预条件子更接近于系数矩阵, 因而结合Krylov子空间方法(如GMRES)有更快的收敛速度.文中分析了GRDF预处理矩阵特征值的一些性质,并用数值算例验证了新预条件子的有效性.     

A modified positive-definite and skew-Hermitian splitting preconditioner for generalized saddle point problems from the Navier-Stokes equation

In this paper, we extend the relaxed positive-definite and skew-Hermitian splitting preconditioner (RPSS) for generalized saddle-point problems in [J.-L. Zhang, C.-Q. Gu and K. Zhang, Appl. Math. Comput. 249(2014)468-479] by introducing an additional parameter. The spectral properties of the presented new preconditioned matrix for generalized saddle-point problem are investigated, meanwhile, the infinite termination merit of the iterative step is also discussed if the Krylov subspace method preconditioned by the modified positive-definite and skew-Hermitian splitting preconditioner (MPSS) is applied. Some numerical experiments illustrate that the efficiency of the proposed new preconditioner.     

A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems

We present a parallel preconditioned iterative solver for large sparse symmetric positive definite linear systems. The preconditioner is constructed as a proper combination of advanced preconditioning strategies. It can be formally seen as being of domain decomposition type with algebraically constructed overlap. Similar to the classical domain decomposition technique, inexact subdomain solvers are used, based on incomplete Cholesky factorization. The proper preconditioner is shown to be near optimal in minimizing the so‐called K‐condition number of the preconditioned matrix. The efficiency of both serial and parallel versions of the solution method is illustrated on a set of benchmark problems in linear elasticity. Copyright © 2002 John Wiley & Sons, Ltd.     

Suitable iterative methods for solving the linear system arising in the three fields domain decomposition method

There are two approaches for applying substructuring preconditioner for the linear system corresponding to the discrete Steklov–Poincaré operator arising in the three fields domain decomposition method for elliptic problems. One of them is to apply the preconditioner in a common way, i.e. using an iterative method such as preconditioned conjugate gradient method [S. Bertoluzza, Substructuring preconditioners for the three fields domain decomposition method, I.A.N.-C.N.R, 2000] and the other one is to apply iterative methods like for instance bi-conjugate gradient method, conjugate gradient square and etc. which are efficient for nonsymmetric systems (the preconditioned system will be nonsymmetric). In this paper, second approach will be followed and extensive numerical tests will be presented which imply that the considered iterative methods are efficient.     

求解分布控制问题的预处理最小残量方法(英文)

通过分析Bai(Bai Z Z.Block preconditioners for elliptic PDE-constrained optimization problems.Computing,2011,91:379-395)给出的离散分布控制问题的块反对角预处理线性系统,提出了该问题的一个等价线性系统,并且运用带有预处理子的最小残量方法对该系统进行求解.理论分析和数值实验结果表明,所提出的预处理最小残量方法对于求解该类椭圆型偏微分方程约束最优分布控制问题非常有效,尤其当正则参数适当小的时候.     

椭圆PDE-约束优化问题的一个预条件子

针对由Galerkin有限元离散椭圆PDE-约束优化问题产生的具有特殊结构的3×3块线性鞍点系统,提出了一个预条件子并给出了预处理矩阵特征值及特征向量的具体表达形式.数值结果表明了该预条件子能够有效地加速Krylov子空间方法的收敛速率,同时也验证了理论结果.     

一类Toeplitz线性代数方程组的预处理GMRES方法

本文研究一类来源于分数阶特征值问题的Toeplitz线性代数方程组的求解.构造Strang循环矩阵作为预处理矩阵来求解该Toeplitz线性代数方程组,分析了预处理后系数矩阵的特征值性质.提出求解该线性代数方程组的预处理广义极小残量法（PGMRES）,并给出该算法的计算量.数值算例表明了该方法的有效性.     

Connection and comparison between frequency shift time integration and a spectral transformation preconditioner

The numerical study of exterior acoustics problems is usually carried out in the frequency domain. Finite element analyses often require the solution of large‐scale algebraic linear systems. For very large problems, sometimes the time domain is used. Implicit time integration requires linear system solves, but these are often far easier than those from the frequency domain. This paper shows a connection between a spectral transformation preconditioner and a frequency shift time integration. This preconditioner is close to the shifted Laplace preconditioner. The preconditioned iterative method appears to be faster than time integration. Copyright © 2008 John Wiley & Sons, Ltd.     

An inexact modified relaxed splitting preconditioner for the generalized saddle point problems from the incompressible Navier-Stokes equations

Based on the modified relaxed splitting (MRS) preconditioner proposed by Fan and Zhu (Appl. Math. Lett. 55, 18–26 2016), an inexact modified relaxed splitting (IMRS) preconditioner is proposed for the generalized saddle point problems arising from the incompressible Navier-Stokes equations. The eigenvalues and eigenvectors of the preconditioned matrix are analyzed, and the convergence property of the corresponding iteration method is also discussed. Numerical experiments are presented to show the effectiveness of the proposed preconditioner when it is used to accelerate the convergence rate of Krylov subspace methods such as GMRES.     

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 geometric theory for preconditioned inverse iteration I: Extrema of the Rayleigh quotient

The discretization of eigenvalue problems for partial differential operators is a major source of matrix eigenvalue problems having very large dimensions, but only some of the smallest eigenvalues together with the eigenvectors are to be determined. Preconditioned inverse iteration (a “matrix-free” method) derives from the well-known inverse iteration procedure in such a way that the associated system of linear equations is solved approximately by using a (multigrid) preconditioner. A new convergence analysis for preconditioned inverse iteration is presented. The preconditioner is assumed to satisfy some bound for the spectral radius of the error propagation matrix resulting in a simple geometric setup. In this first part the case of poorest convergence depending on the choice of the preconditioner is analyzed. In the second part the dependence on all initial vectors having a fixed Rayleigh quotient is considered. The given theory provides sharp convergence estimates for the eigenvalue approximations showing that multigrid eigenvalue/vector computations can be done with comparable efficiency as known from multigrid methods for boundary value problems.     

鞍点问题基于半增广的松弛分裂预条件子

对于(1,1)块为正定的鞍点问题,本文给出了半增广松弛分裂预条件子.文中分析了预条件矩阵特征值分布情况,并用数值实验验证了半增广松弛分裂预条件子的有效性.     

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.     

PRECONDITIONING HIGHER ORDER FINITE ELEMENT SYSTEMS BY ALGEBRAIC MULTIGRID METHOD OF LINEAR ELEMENTS

We present and analyze a robust preconditioned conjugate gradient method for the higher order Lagrangian finite element systems of a class of elliptic problems. An auxiliary linear element stiffness matrix is chosen to be the preconditioner for higher order finite elements. Then an algebraic multigrid method of linear finite element is applied for solving the preconditioner. The optimal condition number which is independent of the mesh size is obtained. Numerical experiments confirm the efficiency of the algorithm.