A hybrid iterative method for symmetric positive definite linear systems

A hybrid iterative scheme that combines the Conjugate Gradient (CG) method with Richardson iteration is presented. This scheme is designed for the solution of linear systems of equations with a large sparse symmetric positive definite matrix. The purpose of the CG iterations is to improve an available approximate solution, as well as to determine an interval that contains all, or at least most, of the eigenvalues of the matrix. This interval is used to compute iteration parameters for Richardson iteration. The attraction of the hybrid scheme is that most of the iterations are carried out by the Richardson method, the simplicity of which makes efficient implementation on modern computers possible. Moreover, the hybrid scheme yields, at no additional computational cost, accurate estimates of the extreme eigenvalues of the matrix. Knowledge of these eigenvalues is essential in some applications.Research supported in part by NSF grant DMS-9409422.Research supported in part by NSF grant DMS-9205531.     

Application of a block modified Chebyshev algorithm to the iterative solution of symmetric linear systems with multiple right hand side vectors

Summary. An adaptive Richardson iteration method is described for the solution of large sparse symmetric positive definite linear systems of equations with multiple right-hand side vectors. This scheme ``learns' about the linear system to be solved by computing inner products of residual matrices during the iterations. These inner products are interpreted as block modified moments. A block version of the modified Chebyshev algorithm is presented which yields a block tridiagonal matrix from the block modified moments and the recursion coefficients of the residual polynomials. The eigenvalues of this block tridiagonal matrix define an interval, which determines the choice of relaxation parameters for Richardson iteration. Only minor modifications are necessary in order to obtain a scheme for the solution of symmetric indefinite linear systems with multiple right-hand side vectors. We outline the changes required. Received April 22, 1993     

The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems

Summary The Chebyshev and second-order Richardson methods are classical iterative schemes for solving linear systems. We consider the convergence analysis of these methods when each step of the iteration is carried out inexactly. This has many applications, since a preconditioned iteration requires, at each step, the solution of a linear system which may be solved inexactly using an inner iteration. We derive an error bound which applies to the general nonsymmetric inexact Chebyshev iteration. We show how this simplifies slightly in the case of a symmetric or skew-symmetric iteration, and we consider both the cases of underestimating and overestimating the spectrum. We show that in the symmetric case, it is actually advantageous to underestimate the spectrum when the spectral radius and the degree of inexactness are both large. This is not true in the case of the skew-symmetric iteration. We show how similar results apply to the Richardson iteration. Finally, we describe numerical experiments which illustrate the results and suggest that the Chebyshev and Richardson methods, with reasonable parameter choices, may be more effective than the conjugate gradient method in the presence of inexactness.This work was supported in part by National Science Foundation Grants DCR-8412314 and DCR-8502014The work of this author was completed while he was on sabbatical leave at the Centre for Mathematical Analysis and Mathematical Sciences Research Institute at the Australian National University, Canberra, Australia     

A fast minimal residual algorithm for shifted unitary matrices

A new iterative scheme is described for the solution of large linear systems of equations with a matrix of the form A = ρU + ζI, where ρ and ζ are constants, U is a unitary matrix and I is the identity matrix. We show that for such matrices a Krylov subspace basis can be generated by recursion formulas with few terms. This leads to a minimal residual algorithm that requires little storage and makes it possible to determine each iterate with fairly little arithmetic work. This algorithm provides a model for iterative methods for non-Hermitian linear systems of equations, in a similar way to the conjugate gradient and conjugate residual algorithms. Our iterative scheme illustrates that results by Faber and Manteuffel [3,4] on the existence of conjugate gradient algorithms with short recurrence relations, and related results by Joubert and Young [13], can be extended.     

Using Chebyshev polynomials and approximate inverse triangular factorizations for preconditioning the conjugate gradient method

In order to precondition a sparse symmetric positive definite matrix, its approximate inverse is examined, which is represented as the product of two sparse mutually adjoint triangular matrices. In this way, the solution of the corresponding system of linear algebraic equations (SLAE) by applying the preconditioned conjugate gradient method (CGM) is reduced to performing only elementary vector operations and calculating sparse matrix-vector products. A method for constructing the above preconditioner is described and analyzed. The triangular factor has a fixed sparsity pattern and is optimal in the sense that the preconditioned matrix has a minimum K-condition number. The use of polynomial preconditioning based on Chebyshev polynomials makes it possible to considerably reduce the amount of scalar product operations (at the cost of an insignificant increase in the total number of arithmetic operations). The possibility of an efficient massively parallel implementation of the resulting method for solving SLAEs is discussed. For a sequential version of this method, the results obtained by solving 56 test problems from the Florida sparse matrix collection (which are large-scale and ill-conditioned) are presented. These results show that the method is highly reliable and has low computational costs.     

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     

An adaptive Richardson iteration method for indefinite linear systems

An adaptive Richardson iteration method is presented for the solution of large linear systems of equations with a sparse, symmetric, nonsingular, indefinite matrix. The relaxation parameters for Richardson iteration are chosen to be reciprocal values of Leja points for a compact setK:=[a,b][c,d], where [a,b] is an interval on the negative real axis and [c, d] is an interval on the positive real axis. Endpoints of these intervals are determined adaptively by computing certain modified moments during the iterations. Computed examples show that this adaptive Richardson method can be competitive with the SYMMLQ and the conjugate residual methods, which are based on the Lanczos process.Dedicated to Germund Dahlquist on the occasion of his 70th birthdayResearch supported in part by the Design and Manufacturing Institute at Stevens Institute of Technology.Research supported in part by NSF grants DMS-9002884 and DMS-9205531.     

非对称线性代数方程组的块向量算法

预条件广义共轭余量法并行和向量计算的关键是预条件计算是否可并行和向量计算，我们利用分而治之的原则，构造了一处块预条件矩阵Ｍ，这里的矩阵Ｍ是通过对线性代数方程组Ａｘ＝ｆ的矩阵Ａ进行块分解，在块分解中利用近似逆技术。这样分解形成的预条件矩阵Ｍ在迭代计算时，可向量或并行计算。     

Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices

We present a probabilistic analysis of two Krylov subspace methods for solving linear systems. We prove a central limit theorem for norms of the residual vectors that are produced by the conjugate gradient and MINRES algorithms when applied to a wide class of sample covariance matrices satisfying some standard moment conditions. The proof involves establishing a four-moment theorem for the so-called spectral measure, implying, in particular, universality for the matrix produced by the Lanczos iteration. The central limit theorem then implies an almost-deterministic iteration count for the iterative methods in question. © 2022 Wiley Periodicals LLC.     

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.     

Multiple right-hand side techniques for the numerical simulation of quasistatic electric and magnetic fields

The simulation of slowly varying transient electric high-voltage fields and magnetic fields requires the repeated and successive solution of high-dimensional linear algebraic systems of equations with identical or near-identical system matrices and different right-hand side vectors. For these solution processes which are required within implicit time integration schemes and nonlinear (quasi-)Newton–Raphson methods an iterative multiple right-hand side (mrhs) scheme is used which recycles vector subspaces resulting from previous preconditioned conjugate gradient iteration runs. The combination of this scheme with a subspace projection extrapolation start value generation scheme is discussed. Numerical results for three-dimensional electric and magnetic field simulations are presented and the efficiency of the new schemes re-using eigenvector information from previous iteration processes with different tolerance criteria are compared to those of standard conjugate gradient iterations.     

An adaptive Chebyshev iterative method\newline for nonsymmetric linear systems based on modified moments

Summary. Large, sparse nonsymmetric systems of linear equations with a matrix whose eigenvalues lie in the right half plane may be solved by an iterative method based on Chebyshev polynomials for an interval in the complex plane. Knowledge of the convex hull of the spectrum of the matrix is required in order to choose parameters upon which the iteration depends. Adaptive Chebyshev algorithms, in which these parameters are determined by using eigenvalue estimates computed by the power method or modifications thereof, have been described by Manteuffel [18]. This paper presents an adaptive Chebyshev iterative method, in which eigenvalue estimates are computed from modified moments determined during the iterations. The computation of eigenvalue estimates from modified moments requires less computer storage than when eigenvalue estimates are computed by a power method and yields faster convergence for many problems. Received May 13, 1992/Revised version received May 13, 1993     

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.     

A higher order richardson scheme for a singularly perturbed semilinear elliptic convection-diffusion equation

The Dirichlet problem on a vertical strip is examined for a singularly perturbed semilinear elliptic convection-diffusion equation. For this problem, the basic nonlinear difference scheme based on the classical approximations on piecewise uniform grids condensing in the vicinity of boundary layers converges ɛ-uniformly with an order at most almost one. The Richardson technique is used to construct a nonlinear scheme that converges ɛ-uniformly with an improved order, namely, at the rate O(N ₁⁻²ln² N ₁ + N ₂⁻²), where N ₁ + 1 and N ₂ + 1 are the number of grid nodes along the x ₁-axis and per unit interval of the x ₂-axis, respectively. This nonlinear basic scheme underlies the linearized iterative scheme, in which the nonlinear term is calculated using the values of the sought function found at the preceding iteration step. The latter scheme is used to construct a linearized iterative Richardson scheme converging ɛ-uniformly with an improved order. Both the basic and improved iterative schemes converge ɛ-uniformly at the rate of a geometric progression as the number of iteration steps grows. The upper and lower solutions to the iterative Richardson schemes are used as indicators, which makes it possible to determine the iteration step at which the same ɛ-uniform accuracy is attained as that of the non-iterative nonlinear Richardson scheme. It is shown that no Richardson schemes exist for the convection-diffusion boundary value problem converging ɛ-uniformly with an order greater than two. Principles are discussed on which the construction of schemes of order greater than two can be based.     

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

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

On the solution of large-scale SDP problems by the modified barrier method using iterative solvers

The limiting factors of second-order methods for large-scale semidefinite optimization are the storage and factorization of the Newton matrix. For a particular algorithm based on the modified barrier method, we propose to use iterative solvers instead of the routinely used direct factorization techniques. The preconditioned conjugate gradient method proves to be a viable alternative for problems with a large number of variables and modest size of the constrained matrix. We further propose to avoid explicit calculation of the Newton matrix either by an implicit scheme in the matrix–vector product or using a finite-difference formula. This leads to huge savings in memory requirements and, for certain problems, to further speed-up of the algorithm. Dedicated to the memory of Jos Sturm.     

Convergence acceleration of preconditioned conjugate gradient solver based on error vector sampling for a sequence of linear systems

In this article, we focus on solving a sequence of linear systems that have identical (or similar) coefficient matrices. For this type of problem, we investigate subspace correction (SC) and deflation methods, which use an auxiliary matrix (subspace) to accelerate the convergence of the iterative method. In practical simulations, these acceleration methods typically work well when the range of the auxiliary matrix contains eigenspaces corresponding to small eigenvalues of the coefficient matrix. We develop a new algebraic auxiliary matrix construction method based on error vector sampling in which eigenvectors with small eigenvalues are efficiently identified in the solution process. We use the generated auxiliary matrix for convergence acceleration in the following solution step. Numerical tests confirm that both SC and deflation methods with the auxiliary matrix can accelerate the solution process of the iterative solver. Furthermore, we examine the applicability of our technique to the estimation of the condition number of the coefficient matrix. We also present the algorithm of the preconditioned conjugate gradient method with condition number estimation.     

An error-free algorithm to solve a linear system of polynomial equations

The paper presents an error-free algorithm to solve a system of linear equations with polynomial coefficients. Modular arithmetic in residual polynomial class and in residual numeric class is employed. The algorithm is iterative and well suited for implementation for computers with vector operations and fast and error-free convolutors.     

On a Chebyshev accelerated splitting iteration method with application to two‐by‐two block linear systems

The Chebyshev accelerated preconditioned modified Hermitian and skew‐Hermitian splitting (CAPMHSS) iteration method is presented for solving the linear systems of equations, which have two‐by‐two block coefficient matrices. We derive an iteration error bound to show that the new method is convergent as long as the eigenvalue bounds are not underestimated. Even when the spectral information is lacking, the CAPMHSS iteration method could be considered as an exponentially converging iterative scheme for certain choices of the method parameters. In this case, the convergence rate is independent of the parameters. Besides, the linear subsystems in each iteration can be solved inexactly, which leads to the inexact CAPMHSS iteration method. The iteration error bound of the inexact method is derived also. We discuss in detail the implementation of CAPMHSS for solving two models arising from the Galerkin finite‐element discretizations of distributed control problems and complex symmetric linear systems. The numerical results show the robustness and the efficiency of the new methods.     

多体系统动力学微分-代数方程L-稳定方法

针对多体系统动力学微分-代数方程形式，在时间区间上构造L-稳定方法，分别基于等距节点、Chebyshev节点和Legendre节点等非等距节点建立求解格式，依据Ehle定理及猜想，与Padé逼近式对比得到待定矩阵和向量，从而获得L-稳定求解公式，循环求解过程采用Newton迭代法计算.以平面双连杆机械臂系统为例，使用L-稳定方法进行数值仿真，通过改变时间区间节点数和步长对各个指标结果进行比较，并与经典Runge-Kutta法对比.结果表明，该方法具有稳定性好、精度高等优点，适用于长时间情况下的多体系统动力学仿真.