Block‐triangular preconditioners for PDE‐constrained optimization

In this paper we investigate the possibility of using a block‐triangular preconditioner for saddle point problems arising in PDE‐constrained optimization. In particular, we focus on a conjugate gradient‐type method introduced by Bramble and Pasciak that uses self‐adjointness of the preconditioned system in a non‐standard inner product. We show when the Chebyshev semi‐iteration is used as a preconditioner for the relevant matrix blocks involving the finite element mass matrix that the main drawback of the Bramble–Pasciak method—the appropriate scaling of the preconditioners—is easily overcome. We present an eigenvalue analysis for the block‐triangular preconditioners that gives convergence bounds in the non‐standard inner product and illustrates their competitiveness on a number of computed examples. Copyright © 2010 John Wiley & Sons, Ltd.     

BCCB preconditioners for systems of BVM‐based numerical integrators

Boundary value methods (BVMs) for ordinary differential equations require the solution of non‐symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A block‐circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. The BCCB preconditioner is shown to be invertible when the BVM is A_k1,k2‐stable. The spectrum of the preconditioned matrix is clustered and therefore, the preconditioned GMRES method converges fast. Moreover, the operation cost in each iteration of the preconditioned GMRES method by using our BCCB preconditioner is less than that required by using block‐circulant preconditioners proposed earlier. In numerical experiments, we compare the number of iterations of various preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.     

Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics

This paper presents a class of limited memory preconditioners (LMP) for solving linear systems of equations with symmetric indefinite matrices and multiple right‐hand sides. These preconditioners based on limited memory quasi‐Newton formulas require a small number k of linearly independent vectors and may be used to improve an existing first‐level preconditioner. The contributions of the paper are threefold. First, we derive a formula to characterize the spectrum of the preconditioned operator. A spectral analysis of the preconditioned matrix shows that the eigenvalues are all real and that the LMP class is able to cluster at least k eigenvalues at 1. Secondly, we show that the eigenvalues of the preconditioned matrix enjoy interlacing properties with respect to the eigenvalues of the original matrix provided that the k linearly independent vectors have been prior projected onto the invariant subspaces associated with the eigenvalues of the original matrix in the open right and left half‐plane, respectively. Third, we focus on theoretical properties of the Ritz‐LMP variant, where Ritz information is used to determine the k vectors. Finally, we illustrate the numerical behaviour of the Ritz limited memory preconditioners on realistic applications in structural mechanics that require the solution of sequences of large‐scale symmetric saddle‐point systems. Numerical experiments show the relevance of the proposed preconditioner leading to a significant decrease in terms of computational operations when solving such sequences of linear systems. A saving of up to 43% in terms of computational effort is obtained on one of these applications. Copyright © 2016 John Wiley & Sons, Ltd.     

Constraint preconditioning for nonsymmetric indefinite linear systems

This paper introduces and presents theoretical analyses of constraint preconditioning via a Schilders'‐like factorization for nonsymmetric saddle‐point problems. We extend the Schilders' factorization of a constraint preconditioner to a nonsymmetric matrix by using a different factorization. The eigenvalue and eigenvector distributions of the preconditioned matrix are determined. The choices of the parameter matrices in the extended Schilders' factorization and the implementation of the preconditioning step are discussed. An upper bound on the degree of the minimum polynomial for the preconditioned matrix and the dimension of the corresponding Krylov subspace are determined, as well as the convergence behavior of a Krylov subspace method such as GMRES. Numerical experiments are presented. Copyright © 2009 John Wiley & Sons, Ltd.     

Quasi‐Toeplitz splitting iteration methods for unsteady space‐fractional diffusion equations

We construct a class of quasi‐Toeplitz splitting iteration methods to solve the two‐sided unsteady space‐fractional diffusion equations with variable coefficients. By making full use of the structural characteristics of the coefficient matrix, the method only requires computational costs of O(n log n) with n denoting the number of degrees of freedom. We develop an appropriate circulant matrix to replace the Toeplitz matrix as a preconditioner. We discuss the spectral properties of the quasi‐circulant splitting preconditioned matrix. Numerical comparisons with existing approaches show that the present method is both effective and efficient when being used as matrix splitting preconditioners for Krylov subspace iteration methods.     

Generalized skew‐Hermitian triangular splitting iteration methods for saddle‐point linear systems

A generalized skew‐Hermitian triangular splitting iteration method is presented for solving non‐Hermitian linear systems with strong skew‐Hermitian parts. We study the convergence of the generalized skew‐Hermitian triangular splitting iteration methods for non‐Hermitian positive definite linear systems, as well as spectrum distribution of the preconditioned matrix with respect to the preconditioner induced from the generalized skew‐Hermitian triangular splitting. Then the generalized skew‐Hermitian triangular splitting iteration method is applied to non‐Hermitian positive semidefinite saddle‐point linear systems, and we prove its convergence under suitable restrictions on the iteration parameters. By specially choosing the values of the iteration parameters, we obtain a few of the existing iteration methods in the literature. Numerical results show that the generalized skew‐Hermitian triangular splitting iteration methods are effective for solving non‐Hermitian saddle‐point linear systems with strong skew‐Hermitian parts. Copyright © 2013 John Wiley & Sons, Ltd.     

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

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

Analysis of a novel preconditioner for a class of p‐level lower rank extracted systems

This paper proposes and studies the performance of a preconditioner suitable for solving a class of symmetric positive definite systems, Âx=b, which we call p‐level lower rank extracted systems (p‐level LRES), by the preconditioned conjugate gradient method. The study of these systems is motivated by the numerical approximation of integral equations with convolution kernels defined on arbitrary p‐dimensional domains. This is in contrast to p‐level Toeplitz systems which only apply to rectangular domains. The coefficient matrix, Â, is a principal submatrix of a p‐level Toeplitz matrix, A, and the preconditioner for the preconditioned conjugate gradient algorithm is provided in terms of the inverse of a p‐level circulant matrix constructed from the elements of A. The preconditioner is shown to yield clustering in the spectrum of the preconditioned matrix which leads to a substantial reduction in the computational cost of solving LRE systems. Copyright © 2006 John Wiley & Sons, Ltd.     

A comparison of abstract versions of deflation,balancing and additive coarse grid correction preconditioners

In this paper we consider various preconditioners for the conjugate gradient (CG) method to solve large linear systems of equations with symmetric positive definite system matrix. We continue the comparison between abstract versions of the deflation, balancing and additive coarse grid correction preconditioning techniques started in (SIAM J. Numer. Anal. 2004; 42 :1631–1647; SIAM J. Sci. Comput. 2006; 27 :1742–1759). There the deflation method is compared with the abstract additive coarse grid correction preconditioner and the abstract balancing preconditioner. Here, we close the triangle between these three methods. First of all, we show that a theoretical comparison of the condition numbers of the abstract additive coarse grid correction and the condition number of the system preconditioned by the abstract balancing preconditioner is not possible. We present a counter example, for which the condition number of the abstract additive coarse grid correction preconditioned system is below the condition number of the system preconditioned with the abstract balancing preconditioner. However, if the CG method is preconditioned by the abstract balancing preconditioner and is started with a special starting vector, the asymptotic convergence behavior of the CG method can be described by the so‐called effective condition number with respect to the starting vector. We prove that this effective condition number of the system preconditioned by the abstract balancing preconditioner is less than or equal to the condition number of the system preconditioned by the abstract additive coarse grid correction method. We also provide a short proof of the relationship between the effective condition number and the convergence of CG. Moreover, we compare the A‐norm of the errors of the iterates given by the different preconditioners and establish the orthogonal invariants of all three types of preconditioners. Copyright © 2008 John Wiley & Sons, Ltd.     

非重迭型区域分解预处理共轭梯度法

本文讨论含有内部交叉点(cross point)的非重迭型区域分解预处理共轭梯度法。称一个点是交叉点,如果有三个或三个以上的子区域以该点做为共同边界点,该点为区域内点。 本文根据在对称正定块对角矩阵类中对角块是对称正定矩阵比较有效的预处理器的理论,通过简单自然的刚度矩阵分裂,基于代数方式,构造了一类预处理器并给出了预处     

Hierarchical Schur complement preconditioner for the stochastic Galerkin finite element methods

Use of the stochastic Galerkin finite element methods leads to large systems of linear equations obtained by the discretization of tensor product solution spaces along their spatial and stochastic dimensions. These systems are typically solved iteratively by a Krylov subspace method. We propose a preconditioner, which takes an advantage of the recursive hierarchy in the structure of the global matrices. In particular, the matrices posses a recursive hierarchical two‐by‐two structure, with one of the submatrices block diagonal. Each of the diagonal blocks in this submatrix is closely related to the deterministic mean‐value problem, and the action of its inverse is in the implementation approximated by inner loops of Krylov iterations. Thus, our hierarchical Schur complement preconditioner combines, on each level in the approximation of the hierarchical structure of the global matrix, the idea of Schur complement with loops for a number of mutually independent inner Krylov iterations, and several matrix–vector multiplications for the off‐diagonal blocks. Neither the global matrix nor the matrix of the preconditioner need to be formed explicitly. The ingredients include only the number of stiffness matrices from the truncated Karhunen–Loève expansion and a good preconditioned for the mean‐value deterministic problem. We provide a condition number bound for a model elliptic problem, and the performance of the method is illustrated by numerical experiments. Copyright © 2013 John Wiley & Sons, Ltd.     

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.     

Right preconditioned MINRES for singular systems†

We consider solving large sparse symmetric singular linear systems. We first introduce an algorithm for right preconditioned minimum residual (MINRES) and prove that its iterates converge to the preconditioner weighted least squares solution without breakdown for an arbitrary right‐hand‐side vector and an arbitrary initial vector even if the linear system is singular and inconsistent. For the special case when the system is consistent, we prove that the iterates converge to a min‐norm solution with respect to the preconditioner if the initial vector is in the range space of the right preconditioned coefficient matrix. Furthermore, we propose a right preconditioned MINRES using symmetric successive over‐relaxation (SSOR) with Eisenstat's trick. Some numerical experiments on semidefinite systems in electromagnetic analysis and so forth indicate that the method is efficient and robust. Finally, we show that the residual norm can be further reduced by restarting the iterations.     

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.     

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.     

广义块Toeplitz特征值问题的基于sine变换的预处理子

在求块Toeplitz矩阵束（Amn，Bmn）特征值的Lanczos过程中，通过对移位块Toepltz矩阵Amn-ρBmn进行基于sine变换的块预处理，从而改进了位移块Toeplitz矩阵的谱分布，加速了Lanczos过程的收敛速度．该块预处理方法能通过快速算法有效快速执行．本文证明了预处理后Lanczos过程收敛迅速，并通过实验证明该算法求解大规模矩阵问题尤其有效．     

An improved block splitting preconditioner for complex symmetric indefinite linear systems

In this paper, an improved block splitting preconditioner for a class of complex symmetric indefinite linear systems is proposed. By adopting two iteration parameters and the relaxation technique, the new preconditioner not only remains the same computational cost with the block preconditioners but also is much closer to the original coefficient matrix. The theoretical analysis shows that the corresponding iteration method is convergent under suitable conditions and the preconditioned matrix can have well-clustered eigenvalues around (0,1) with a reasonable choice of the relaxation parameters. An estimate concerning the dimension of the Krylov subspace for the preconditioned matrix is also obtained. Finally, some numerical experiments are presented to illustrate the effectiveness of the presented preconditioner.     

Fast solvers with block‐diagonal preconditioners for linear FEM–BEM coupling

The purpose of this paper is to present optimal preconditioned iterative methods to solve indefinite linear systems of equations arising from symmetric coupling of finite elements and boundary elements. This is a block‐diagonal preconditioner together with a conjugate residual method and a preconditioned inner–outer iteration. We prove the efficiency of these methods by showing that the number of iterations to preserve a given accuracy is bounded independent of the number of unknowns. Numerical examples underline the efficiency of these methods. Copyright © 2008 John Wiley & Sons, Ltd.     

Comparison results of the preconditioned AOR methods for L-matrices

In this paper, we first provide comparison results of several types of the preconditioned AOR (PAOR) methods for solving a linear system whose coefficient matrix is an L-matrix satisfying some weaker conditions than those used in the recent literature. Next, we propose an application of PAOR method to a preconditioner of Krylov subspace method. Lastly, numerical results are provided to show that Krylov subspace method with the PAOR preconditioner performs quite well as compared with the ILU (0) preconditioner.