A QUASI-MINIMAL RESIDUAL VARIANT OF THE IOM (q) FOR LARGE UNSYMMETRIC LINEAR SYSTEMS

1　IntroductionThe solution of large N× N nonsingular unsymmetric( non-Hermitian) sparse sys-tems of linear equationsAx =b, ( 1 )is one of the most frequently encountered tasks in numerical computations.For example,such systems arise from finite difference or finite element approximations to partial differ-ential equationsA major class of methods for solving ( 1 ) is Krylov subspace or conjugate gradienttype methods.Most successful scheme of these methods are based on the orthogonal pro-jec…     

A QMR-based interior-point algorithm for solving linear programs

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2×2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3×3-block systems to symmetric 2×2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.     

A look-ahead algorithm for the solution of general Hankel systems

Summary The solution of systems of linear equations with Hankel coefficient matrices can be computed with onlyO(n ²) arithmetic operations, as compared toO(n ³) operations for the general cases. However, the classical Hankel solvers require the nonsingularity of all leading principal submatrices of the Hankel matrix. The known extensions of these algorithms to general Hankel systems can handle only exactly singular submatrices, but not ill-conditioned ones, and hence they are numerically unstable. In this paper, a stable procedure for solving general nonsingular Hankel systems is presented, using a look-ahead technique to skip over singular or ill-conditioned submatrices. The proposed approach is based on a look-ahead variant of the nonsymmetric Lanczos process that was recently developed by Freund, Gutknecht, and Nachtigal. We first derive a somewhat more general formulation of this look-ahead Lanczos algorithm in terms of formally orthogonal polynomials, which then yields the look-ahead Hankel solver as a special case. We prove some general properties of the resulting look-ahead algorithm for formally orthogonal polynomials. These results are then utilized in the implementation of the Hankel solver. We report some numerical experiments for Hankel systems with ill-conditioned submatrices.The research of the first author was supported by DARPA via Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).The research of the second author was supported in part by NSF grant DRC-8412314 and Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).     

On deflation and singular symmetric positive semi-definite matrices

For various applications, it is well-known that the deflated ICCG is an efficient method for solving linear systems with invertible coefficient matrix. We propose two equivalent variants of this deflated ICCG which can also solve linear systems with singular coefficient matrix, arising from discretization of the discontinuous Poisson equation with Neumann boundary conditions. It is demonstrated both theoretically and numerically that the resulting methods accelerate the convergence of the iterative process.     

Semiconvergence of extrapolated iterative methods for singular linear systems

In this paper, we discuss convergence of the extrapolated iterative methods for solving singular linear systems. A general principle of extrapolation is presented. The semiconvergence of an extrapolated method induced by a regular splitting and a nonnegative splitting is proved whenever the coefficient matrix A is a singular M-matrix with ‘property c’ and an irreducible singular M-matrix, respectively. Since the (generalized, block) JOR and AOR methods are respectively the extrapolated methods of the (generalized, block) Jacobi and SOR methods, so the semiconvergence of the (generalized, block) JOR and AOR methods for solving general singular systems are proved. Furthermore, the semiconvergence of the extrapolated power method, the (block) JOR, AOR and SOR methods for solving Markov chains are discussed.     

CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm

The Generalized Minimal Residual (GMRES) method and the Quasi-Minimal Residual (QMR) method are two Krylov methods for solving linear systems. The main difference between these methods is the generation of the basis vectors for the Krylov subspace. The GMRES method uses the Arnoldi process while QMR uses the Lanczos algorithm for constructing a basis of the Krylov subspace. In this paper we give a new method similar to QMR but based on the Hessenberg process instead of the Lanczos process. We call the new method the CMRH method. The CMRH method is less expensive and requires slightly less storage than GMRES. Numerical experiments suggest that it has behaviour similar to GMRES. This revised version was published online in June 2006 with corrections to the Cover Date.     

Adaptive solution of infinite linear systems by Krylov subspace methods

In this paper we consider the problem of approximating the solution of infinite linear systems, finitely expressed by a sparse coefficient matrix. We analyse an algorithm based on Krylov subspace methods embedded in an adaptive enlargement scheme. The management of the algorithm is not trivial, due to the irregular convergence behaviour frequently displayed by Krylov subspace methods for nonsymmetric systems. Numerical experiments, carried out on several test problems, indicate that the more robust methods, such as GMRES and QMR, embedded in the adaptive enlargement scheme, exhibit good performances.     

On the convergence of general stationary iterative methods for range‐Hermitian singular linear systems

General stationary iterative methods with a singular matrix M for solving range‐Hermitian singular linear systems are presented, some convergence conditions and the representation of the solution are also given. It can be verified that the general Ortega–Plemmons theorem and Keller theorem for the singular matrix M still hold. Furthermore, the singular matrix M can act as a good preconditioner for solving range‐Hermitian linear systems. Numerical results have demonstrated the effectiveness of the general stationary iterations and the singular preconditioner M. Copyright © 2009 John Wiley & Sons, Ltd.     

A generalized inverse method for asymptotic linear programming

Consider a linear program in which the entries of the coefficient matrix vary linearly with time. To study the behavior of optimal solutions as time goes to infinity, it is convenient to express the inverse of the basis matrix as a series expansion of powers of the time parameter. We show that an algorithm of Wilkinson (1982) for solving singular differential equations can be used to obtain such an expansion efficiently. The resolvent expansions of dynamic programming are a special case of this method.     

Sequential Systems of Linear Equations Algorithm for Nonlinear Optimization Problems with General Constraints

In Ref. 1, a new superlinearly convergent algorithm of sequential systems of linear equations (SSLE) for nonlinear optimization problems with inequality constraints was proposed. At each iteration, this new algorithm only needs to solve four systems of linear equations having the same coefficient matrix, which is much less than the amount of computation required for existing SQP algorithms. Moreover, unlike the quadratic programming subproblems of the SQP algorithms (which may not have a solution), the subproblems of the SSLE algorithm are always solvable. In Ref. 2, it is shown that the new algorithm can also be used to deal with nonlinear optimization problems having both equality and inequality constraints, by solving an auxiliary problem. But the algorithm of Ref. 2 has to perform a pivoting operation to adjust the penalty parameter per iteration. In this paper, we improve the work of Ref. 2 and present a new algorithm of sequential systems of linear equations for general nonlinear optimization problems. This new algorithm preserves the advantages of the SSLE algorithms, while at the same time overcoming the aforementioned shortcomings. Some numerical results are also reported.     

Wavelet analysis method for solving linear and nonlinear singular boundary value problems

In this paper, a robust and accurate algorithm for solving both linear and nonlinear singular boundary value problems is proposed. We introduce the Chebyshev wavelets operational matrix of derivative and product operation matrix. Chebyshev wavelets expansions together with operational matrix of derivative are employed to solve ordinary differential equations in which, at least, one of the coefficient functions or solution function is not analytic. Several examples are included to illustrate the efficiency and accuracy of the proposed method.     

Conjugate gradient and minimal residual methods for solving symmetric indefinite systems

Norm-minimizing-type methods for solving large sparse linear systems with symmetric and indefinite coefficient matrices are considered. The Krylov subspace can be generated by either the Lanczos approach, such as the methods MINRES, GMRES and QMR, or by a conjugate-gradient approach. Here, we propose an algorithm based on the latter approach. Some relations among the search directions and the residuals, and how the search directions are related to the Krylov subspace are investigated. Numerical experiments are reported to verify the convergence properties.     

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.     

New GMRES(k)-Type Algorithms with Explicit Restarts and the Analysis of Their Convergence Properties Based on Matrix Relations in QR Form

The paper considers the problem of constructing a basic iterative scheme for solving systems of linear algebraic equations with unsymmetric and indefinite coefficient matrices. A new GMRES-type algorithm with explicit restarts is suggested. When restarting, this algorithm takes into account the spectral/singular data transferred using orthogonal matrix relations in the so-called QR form, which arise when performing inner iterations of Arnoldi type. The main idea of the algorithm developed is to organize inner iterations and the filtering of directions before restarting in such a way that, from one restart to another, matrix relations effectively accumulate information concerning the current approximate solution and, simultaneously, spectral/singular data, which allow the algorithm to converge with a rate comparable with that of the GMRES algorithm without restarts. Convergence theory is provided for the case of nonsingular, unsymmetric, and indefinite matrices. A bound for the rate of decrease of the residual in the course of inner Arnoldi-type iterations is obtained. This bound depends on the spectral/singular characterization of the subspace spanned by the directions retained upon filtering and is used in developing efficient filtering procedures. Numerical results are provided. Bibliography: 9 titles.     

A parallel implementation of the CMRH method for dense linear systems

This paper presents an implementation of the CMRH (Changing Minimal Residual method based on the Hessenberg process) iterative method suitable for parallel architectures. CMRH is an alternative to GMRES and QMR, the well-known Krylov methods for solving linear systems with non-symmetric coefficient matrices. CMRH generates a (non orthogonal) basis of the Krylov subspace through the Hessenberg process. On dense matrices, it requires less storage than GMRES. Parallel numerical experiments on a distributed memory computer with up to 16 processors are shown on some applications related to the solution of dense linear systems of equations. A comparison with the GMRES method is also provided on those test examples.     

QMR: a quasi-minimal residual method for non-Hermitian linear systems

Summary The biconjugate gradient (BCG) method is the natural generalization of the classical conjugate gradient algorithm for Hermitian positive definite matrices to general non-Hermitian linear systems. Unfortunately, the original BCG algorithm is susceptible to possible breakdowns and numerical instabilities. In this paper, we present a novel BCG-like approach, the quasi-minimal residual (QMR) method, which overcomes the problems of BCG. An implementation of QMR based on a look-ahead version of the nonsymmetric Lanczos algorithm is proposed. It is shown how BCG iterates can be recovered stably from the QMR process. Some further properties of the QMR approach are given and an error bound is presented. Finally, numerical experiments are reported.This work was supported in part by DARPA via Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).     

A note on preconditioned GMRES for solving singular linear systems

For solving a singular linear system Ax=b by GMRES, it is shown in the literature that if A is range-symmetric, then GMRES converges safely to a solution. In this paper we consider preconditioned GMRES for solving a singular linear system, we construct preconditioners by so-called proper splittings, which can ensure that the coefficient matrix of the preconditioned system is range-symmetric.     

Monotone Convergence of Iterative Methods for Singular Linear Systems

In this paper, monotonicity of iterative methods for solving general solvable singularly systems is discussed. The monotonicity results given by Berman, Plemmons, and Semal are generalized to singular systems. It is shown that for an iterative method introduced by a nonnegative splitting of the coefficient matrix there exist some initial guesses such that the iterative sequence converges towards a solution of the system from below or from above. The monotonicity of the block Gauss-Seidel method for solving a p-cyclic system and Markov chain is considered.     

基于Lanczos双A-正交的一种修正的QMR算法

本文研究了基于Lanczos双正交过程的拟极小残量法(QMR).将QMR算法中的Lanczos双正交过程用Lanczos双A-正交过程代替,利用该算法得到的近似解与最后一个基向量的线性组合来作为新的近似解,使新近似解的残差范数满足一个一维极小化问题,从而得到一种基于Lanczos双A-正交的修正的QMR算法.数值试验表明,对于某些大型线性稀疏方程组,新算法比QMR算法收敛快得多.     

A look-ahead Bareiss algorithm for general Toeplitz matrices

Summary. The Bareiss algorithm is one of the classical fast solvers for systems of linear equations with Toeplitz coefficient matrices. The method takes advantage of the special structure, and it computes the solution of a Toeplitz system of order~ with only~ arithmetic operations, instead of~ operations. However, the original Bareiss algorithm requires that all leading principal submatrices be nonsingular, and the algorithm is numerically unstable if singular or ill-conditioned submatrices occur. In this paper, an extension of the Bareiss algorithm to general Toeplitz systems is presented. Using look-ahead techniques, the proposed algorithm can skip over arbitrary blocks of singular or ill-conditioned submatrices, and at the same time, it still fully exploits the Toeplitz structure. Implementation details and operations counts are given, and numerical experiments are reported. We also discuss special versions of the proposed look-ahead Bareiss algorithm for Hermitian indefinite Toeplitz systems and banded Toeplitz systems. Received August 27, 1993 / Revised version received March 1994