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.     

Minimum residual methods for augmented systems

For large systems of linear equations, iterative methods provide attractive solution techniques. We describe the applicability and convergence of iterative methods of Krylov subspace type for an important class of symmetric and indefinite matrix problems, namely augmented (or KKT) systems. Specifically, we consider preconditioned minimum residual methods and discuss indefinite versus positive definite preconditioning. For a natural choice of starting vector we prove that when the definite and indenfinite preconditioners are related in the obvious way, MINRES (which is applicable in the case of positive definite preconditioning) and full GMRES (which is applicable in the case of indefinite preconditioning) give residual vectors with identical Euclidean norm at each iteration. Moreover, we show that the convergence of both methods is related to a system of normal equations for which the LSQR algorithm can be employed. As a side result, we give a rare example of a non-trivial normal(1) matrix where the corresponding inner product is explicitly known: a conjugate gradient method therefore exists and can be employed in this case. This work was supported by British Council/German Academic Exchange Service Research Collaboration Project 465 and NATO Collaborative Research Grant CRG 960782     

关于具优势对称部分的不定线性代数方程组的分裂极小残量算法

１．引 言 考虑大型稀疏线性代数方程组 为利用系数矩阵的稀疏结构以尽可能减少存储空间和计算开销，Ｋｒｙｌｏｖ子空间迭代算法［１，１６，２３］及其预处理变型［６，８，１３，１８，１９］通常是求解（１）的有效而实用的方法．当系数矩阵对称正定时，共轭梯度法（ＣＧ（     

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.     

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.     

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.     

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

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

TWO ALGORITHMS FOR SYMMETRIC LINEAR SYSTEMS WITH MULTIPLE RIGHT-HAND SIDES

1　ＩｎｔｒｏｄｕｃｔｉｏｎＩｎｍａｎｙａｐｐｌｉｃａｔｉｏｎｓｗｅｎｅｅｄｔｏｓｏｌｖｅｍｕｌｔｉｐｌｅｓｙｓｔｅｍｓｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓＡｘ(ｉ) =ｂ(ｉ) ,ｉ=1,… ,ｓ (1)ｗｉｔｈｔｈｅｓａｍｅｎ×ｎｒｅａｌｓｙｍｍｅｔｒｉｃｃｏｅｆｆｉｃｉｅｎｔｍａｔｒｉｘＡ ,ｂｕｔｓｄｉｆｆｅｒｅｎｔｒｉｇｈｔ ｈａｎｄｓｉｄｅｓｂ(ｉ) (ｉ=1,… ,ｓ) .Ｉｆａｌｌｏｆｔｈｅｒｉｇｈｔ ｈａｎｄｓｉｄｅｓａｒｅａｖａｉｌａｂｌｅｓｉｍｕｌｔａｎｅｏｕｓｌｙ ,ｔｈｅｎｔｈｅｓｅｓｌｉｎｅａｒｓｙｓｔｅ…     

Incomplete block factorization preconditioning for indefinite elliptic problems

Summary. The application of the finite difference method to approximate the solution of an indefinite elliptic problem produces a linear system whose coefficient matrix is block tridiagonal and symmetric indefinite. Such a linear system can be solved efficiently by a conjugate residual method, particularly when combined with a good preconditioner. We show that specific incomplete block factorization exists for the indefinite matrix if the mesh size is reasonably small, and that this factorization can serve as an efficient preconditioner. Some efforts are made to estimate the eigenvalues of the preconditioned matrix. Numerical results are also given. Received November 21, 1995 / Revised version received February 2, 1998 / Published online July 28, 1999     

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.     

Strang-Type Preconditioners for Solving Linear Systems from Delay Differential Equations

We consider the solution of delay differential equations (DDEs) by using boundary value methods (BVMs). These methods require the solution of one or more nonsymmetric, large and sparse linear systems. The GMRES method with the Strang-type block-circulant preconditioner is proposed for solving these linear systems. We show that if a P _{k 1},k ₂-stable BVM is used for solving an m-by-m system of DDEs, then our preconditioner is invertible and all the eigenvalues of the preconditioned system are clustered around 1. It follows that when the GMRES method is applied to solving the preconditioned systems, the method may converge fast. Numerical results are given to illustrate the effectiveness of our methods.     

DOMAIN DECOMPOSITION PRECONDITIONERS FOR SECOND-ORDER HYPERBOLIC EQUATIONS ON L-SHAPED REGIONS

Linear systems arising from implicit time discretizations and finite difference space discretizations of second-order hyperbolic equations on L-shaped region are considered. We analyse the use of domain deocmposilion preconditioner.s for the solution of linear systems via the preconditioned conjugate gradient method. For the constant-coefficient second-order hyperbolic equaions with initial and Dirichlet boundary conditions,we prove that the conditionnumber of the preconditioned interface system is bounded by 2+x2 2+0.46x2 where x is the quo-tient between the lime and space steps. Such condition number produces a convergence rale that is independent of gridsize and aspect ratios. The results could be extended to parabolic equations.     

GENUINE-OPTIMAL CIRCULANT PRECONDITIONERS FOR WIENER-HOPF EQUATIONS

1. IntroductionWienerHopf equations are integral equations defined on the haif line:where rr > 0, a(.) C L1(ro and g(.) E L2(at). Here R = (--oo,oo) and ty [0,oo). Inou-r discussions, we assume that a(.) is colljugate symmetric, i.e. a(--t) = a(t). WienerHop f equations arise in a variety of practical aPplicatiolls in mathematics and ellgineering, forinstance, in the linear prediction problems fOr stationary stochastic processes [8, pp.145--146],diffuSion problems and scattering problems […     

An iterative two-step algorithm for linear complementarity problems

Summary. We propose an algorithm for the numerical solution of large-scale symmetric positive-definite linear complementarity problems. Each step of the algorithm combines an application of the successive overrelaxation method with projection (to determine an approximation of the optimal active set) with the preconditioned conjugate gradient method (to solve the reduced residual systems of linear equations). Convergence of the iterates to the solution is proved. In the experimental part we compare the efficiency of the algorithm with several other methods. As test example we consider the obstacle problem with different obstacles. For problems of dimension up to 24\,000 variables, the algorithm finds the solution in less then 7 iterations, where each iteration requires about 10 matrix-vector multiplications. Received July 14, 1993 / Revised version received February 1994     

Sine transform based preconditioning techniques for space fractional diffusion equations

We study the preconditioned iterative methods for the linear systems arising from the numerical solution of the multi-dimensional space fractional diffusion equations. A sine transform based preconditioning technique is developed according to the symmetric and skew-symmetric splitting of the Toeplitz factor in the resulting coefficient matrix. Theoretical analyses show that the upper bound of relative residual norm of the GMRES method when applied to the preconditioned linear system is mesh-independent which implies the linear convergence. Numerical experiments are carried out to illustrate the correctness of the theoretical results and the effectiveness of the proposed preconditioning technique.     

Inverse Iteration: An Alternative Form

Rayleigh quotient inverse iteration (RQI) is examined from the standpoint of incremental vectors. By choosing such a vector orthogonal to the eigenvector iterate at the mth step, χ_m, a system of linear equations is derived; solving the system is shown to be equivalent to RQI. The residual norm converges to zero for Hermitian matrices, and the coefficient matrix does not in general converge to a singular matrix as it does in RQI. Furthermore, the procedure described produces successive vector iterates whose norms do not in general become large (when m→∞) as they do with RQI.     

A preconditioner for generalized saddle point problems: Application to 3D stationary Navier‐Stokes equations

In this article we consider the stationary Navier‐Stokes system discretized by finite element methods which do not satisfy the inf‐sup condition. These discretizations typically take the form of a variational problem with stabilization terms. Such a problem may be transformed by iteration methods into a sequence of linear, Oseen‐type variational problems. On the algebraic level, these problems belong to a certain class of linear systems with nonsymmetric system matrices (“generalized saddle point problems”). We show that if the underlying finite element spaces satisfy a generalized inf‐sup condition, these problems have a unique solution. Moreover, we introduce a block triangular preconditioner and we show how the eigenvalue bounds of the preconditioned system matrix depend on the coercivity constant and continuity bounds of the bilinear forms arising in the variational problem. Finally we prove that the stabilized P1‐P1 finite element method proposed by Rebollo is covered by our theory and we show that the condition number of the preconditioned system matrix is independent of the mesh size. Numerical tests with 3D stationary Navier‐Stokes flows confirm our results. © 2006 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2006     

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 preconditioned low‐rank CG method for parameter‐dependent Lyapunov matrix equations

This paper is concerned with the numerical solution of symmetric large‐scale Lyapunov equations with low‐rank right‐hand sides and coefficient matrices depending on a parameter. Specifically, we consider the situation when the parameter dependence is sufficiently smooth, and the aim is to compute solutions for many different parameter samples. On the basis of existing results for Lyapunov equations and parameter‐dependent linear systems, we prove that the tensor containing all solution samples typically allows for an excellent low multilinear rank approximation. Stacking all sampled equations into one huge linear system, this fact can be exploited by combining the preconditioned CG method with low‐rank truncation. Our approach is flexible enough to allow for a variety of preconditioners based, for example, on the sign function iteration or the alternating direction implicit method. Copyright © 2013 John Wiley & Sons, Ltd.     

A new block preconditioner for complex symmetric indefinite linear systems

Using the equivalent block two-by-two real linear systems and relaxing technique, we establish a new block preconditioner for a class of complex symmetric indefinite linear systems. The new preconditioner is much closer to the original block two-by-two coefficient matrix than the Hermitian and skew-Hermitian splitting (HSS) preconditioner. We analyze the spectral properties of the new preconditioned matrix, discuss the eigenvalue distribution and derive an upper bound for the degree of its minimal polynomial. Finally, some numerical examples are provided to show the effectiveness and robustness of our proposed preconditioner.