Nested splitting CG-like iterative method for solving the continuous Sylvester equation and preconditioning

We present a nested splitting conjugate gradient iteration method for solving large sparse continuous Sylvester equation, in which both coefficient matrices are (non-Hermitian) positive semi-definite, and at least one of them is positive definite. This method is actually inner/outer iterations, which employs the Sylvester conjugate gradient method as inner iteration to approximate each outer iterate, while each outer iteration is induced by a convergent and Hermitian positive definite splitting of the coefficient matrices. Convergence conditions of this method are studied and numerical experiments show the efficiency of this method. In addition, we show that the quasi-Hermitian splitting can induce accurate, robust and effective preconditioned Krylov subspace methods.     

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

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

A general finite element preconditioning for the conjugate gradient method

Discretizing a symmetric elliptic boundary value problem by a finite element method results in a system of linear equations with a symmetric positive definite coefficient matrix. This system can be solved iteratively by a preconditioned conjugate gradient method. In this paper a preconditioning matrix is proposed that can be constructed for all finite element methods if a mild condition for the node numbering is fulfilled. Such a numbering can be constructed using a variant of the reverse Cuthill-McKee algorithm.     

On decomposition-based block preconditioned iterative methods for half-quadratic image restoration

Image restoration is a fundamental problem in image processing. Except for many different filters applied to obtain a restored image in image restoration, a degraded image can often be recovered efficiently by minimizing a cost function which consists of a data-fidelity term and a regularization term. In specific, half-quadratic regularization can effectively preserve image edges in the recovered images and a fixed-point iteration method is usually employed to solve the minimization problem. In this paper, the Newton method is applied to solve the half-quadratic regularization image restoration problem. And at each step of the Newton method, a structured linear system of a symmetric positive definite coefficient matrix arises. We design two different decomposition-based block preconditioning matrices by considering the special structure of the coefficient matrix and apply the preconditioned conjugate gradient method to solve this linear system. Theoretical analysis shows the eigenvector properties and the spectral bounds for the preconditioned matrices. The method used to analyze the spectral distribution of the preconditioned matrix and the correspondingly obtained spectral bounds are different from those in the literature. The experimental results also demonstrate that the decomposition-based block preconditioned conjugate gradient method is efficient for solving the half-quadratic regularization image restoration in terms of the numerical performance and image recovering quality.     

Multisplitting preconditioners for a symmetric positive definite matrix

We study convergence of multisplitting method associated with a block diagonal conformable multisplitting for solving a linear system whose coefficient matrix is a symmetric positive definite matrix which is not an H-matrix. Next, we study the validity ofm-step multisplitting polynomial preconditioners which will be used in the preconditioned conjugate gradient method.     

Preconditioned Iterative Methods for Algebraic Systems from Multiplicative Half-Quadratic Regularization Image Restorations

<正>Image restoration is often solved by minimizing an energy function consisting of a data-fidelity term and a regularization term.A regularized convex term can usually preserve the image edges well in the restored image.In this paper,we consider a class of convex and edge-preserving regularization functions,i.e.,multiplicative half-quadratic regularizations,and we use the Newton method to solve the correspondingly reduced systems of nonlinear equations.At each Newton iterate,the preconditioned conjugate gradient method,incorporated with a constraint preconditioner,is employed to solve the structured Newton equation that has a symmetric positive definite coefficient matrix. The eigenvalue bounds of the preconditioned matrix are deliberately derived,which can be used to estimate the convergence speed of the preconditioned conjugate gradient method.We use experimental results to demonstrate that this new approach is efficient, and the effect of image restoration is reasonably well.     

Combination of Jacobi–Davidson and conjugate gradients for the partial symmetric eigenproblem

To compute the smallest eigenvalues and associated eigenvectors of a real symmetric matrix, we consider the Jacobi–Davidson method with inner preconditioned conjugate gradient iterations for the arising linear systems. We show that the coefficient matrix of these systems is indeed positive definite with the smallest eigenvalue bounded away from zero. We also establish a relation between the residual norm reduction in these inner linear systems and the convergence of the outer process towards the desired eigenpair. From a theoretical point of view, this allows to prove the optimality of the method, in the sense that solving the eigenproblem implies only a moderate overhead compared with solving a linear system. From a practical point of view, this allows to set up a stopping strategy for the inner iterations that minimizes this overhead by exiting precisely at the moment where further progress would be useless with respect to the convergence of the outer process. These results are numerically illustrated on some model example. Direct comparison with some other eigensolvers is also provided. Copyright © 2001 John Wiley & Sons, Ltd.     

求解带Toeplitz矩阵的线性互补问题的一类预处理模系矩阵分裂迭代法

针对系数矩阵为对称正定Toeplitz矩阵的线性互补问题,本文提出了一类预处理模系矩阵分裂迭代方法.先通过变量替换将线性互补问题转化为一类非线性方程组,然后选取Strang或T.Chan循环矩阵作为预优矩阵,利用共轭梯度法进行求解.我们分析了该方法的收敛性.数值实验表明,该方法是高效可行的.     

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     

A real-valued block conjugate gradient type method for solving complex symmetric linear systems with multiple right-hand sides

We consider solving complex symmetric linear systems with multiple right-hand sides. We assume that the coefficient matrix has indefinite real part and positive definite imaginary part. We propose a new block conjugate gradient type method based on the Schur complement of a certain 2-by-2 real block form. The algorithm of the proposed method consists of building blocks that involve only real arithmetic with real symmetric matrices of the original size. We also present the convergence property of the proposed method and an efficient algorithmic implementation. In numerical experiments, we compare our method to a complex-valued direct solver, and a preconditioned and nonpreconditioned block Krylov method that uses complex arithmetic.     

Preconditioned iterative methods for a class of nonlinear eigenvalue problems

This paper proposes new iterative methods for the efficient computation of the smallest eigenvalue of symmetric nonlinear matrix eigenvalue problems of large order with a monotone dependence on the spectral parameter. Monotone nonlinear eigenvalue problems for differential equations have important applications in mechanics and physics. The discretization of these eigenvalue problems leads to nonlinear eigenvalue problems with very large sparse ill-conditioned matrices monotonically depending on the spectral parameter. To compute the smallest eigenvalue of large-scale matrix nonlinear eigenvalue problems, we suggest preconditioned iterative methods: preconditioned simple iteration method, preconditioned steepest descent method, and preconditioned conjugate gradient method. These methods use only matrix-vector multiplications, preconditioner-vector multiplications, linear operations with vectors, and inner products of vectors. We investigate the convergence and derive grid-independent error estimates for these methods. Numerical experiments demonstrate the practical effectiveness of the proposed methods for a model problem.     

对称正定Toeplitz方程组的多级迭代求解

二级迭代法亦称内外迭代法. 多级迭代法由多个二级迭代嵌套而成.这些方法特别适合于并行计算,同时可以理解为古典迭代法的延伸或共轭梯度法的预处理子.本文讨论了对称正定Toeplitz线性方程组多级迭代法. 首先,基于Toeplitz矩阵的结构, 我们给出了多级块Jacobi分裂,然后证明了每一级分裂均为P-正则分裂, 并证明了当每一级内迭代次数均为偶数时,迭代法的收敛性. 最后通过数值实例验证了此方法的有效性.     

Block two-stage preconditioners

Linear systems of the form Ax = b, where the matrix A is symmetric and positive definite, often arise from the discretization of elliptic partial differential equations. A very successful method for solving these linear systems is the preconditioned conjugate gradient method. In this paper, we study parallel preconditioners for the conjugate gradient method based on the block two-stage iterative methods. Sufficient conditions for the validity of these preconditioners are given. Computational results of these preconditioned conjugate gradient methods on two parallel computing systems are presented.     

一类弱非线性方程组的Picard-MHSS迭代方法

修正的Hermite/反Hermite分裂(MHSS)迭代方法是一类求解大型稀疏复对称线性代数方程组的无条件收敛的迭代算法.基于非线性代数方程组的特殊结构和性质,我们选取Picard迭代为外迭代方法,MHSS迭代作为内迭代方法,构造了求解大型稀疏弱非线性代数方程组的Picard-MHSS和非线性MHSS-like方法.这两类方法的优点是不需要在每次迭代时均精确计算和存储Jacobi矩阵,仅需要在迭代过程中求解两个常系数实对称正定子线性方程组.除此之外,在一定条件下,给出了两类方法的局部收敛性定理.数值结果证明了这两类方法是可行、有效和稳健的.     

A SHIFT-SPLITTING PRECONDITIONER FOR NON-HERMITIAN POSITIVE DEFINITE MATRICES

A shift splitting concept is introduced and, correspondingly, a shift-splitting iteration scheme and a shift-splitting preconditioner are presented, for solving the large sparse system of linear equations of which the coefficient matrix is an ill-conditioned non-Hermitian positive definite matrix. The convergence property of the shift-splitting iteration method and the eigenvalue distribution of the shift-splitting preconditioned matrix are discussed in depth, and the best possible choice of the shift is investigated in detail. Numerical computations show that the shift-splitting preconditioner can induce accurate, robust and effective preconditioned Krylov subspace iteration methods for solving the large sparse non-Hermitian positive definite systems of linear equations.     

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.     

Regularizing properties of a truncated newton-cg algorithm for nonlinear inverse problems

This paper develops truncated Newton methods as an appropriate tool for nonlinear inverse problems which are ill-posed in the sense of Hadamard. In each Newton step an approximate solution for the linearized problem is computed with the conjugate gradient method as an inner iteration. The conjugate gradient iteration is terminated when the residual has been reduced to a prescribed percentage. Under certain assumptions on the nonlinear operator it is shown that the algorithm converges and is stable if the discrepancy principle is used to terminate the outer iteration. These assumptions are fulfilled, e.g., for the inverse problem of identifying the diffusion coefficient in a parabolic differential equation from distributed data.     

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 new single-step iteration method for solving complex symmetric linear systems

For solving a class of complex symmetric linear systems, we introduce a new single-step iteration method, which can be taken as a fixed-point iteration adding the asymptotical error (FPAE). In order to accelerate the convergence, we further develop the parameterized variant of the FPAE (PFPAE) iteration method. Each iteration of the FPAE and the PFPAE methods requires the solution of only one linear system with a real symmetric positive definite coefficient matrix. Under suitable conditions, we derive the spectral radius of the FPAE and the PFPAE iteration matrices, and discuss the quasi-optimal parameters which minimize the above spectral radius. Numerical tests support the contention that the PFPAE iteration method has comparable advantage over some other commonly used iteration methods, particularly when the experimental optimal parameters are not used.