A composite step bi-conjugate gradient algorithm for nonsymmetric linear systems

The Bi-Conjugate Gradient (BCG) algorithm is the simplest and most natural generalization of the classical conjugate gradient method for solving nonsymmetric linear systems. It is well-known that the method suffers from two kinds of breakdowns. The first is due to the breakdown of the underlying Lanczos process and the second is due to the fact that some iterates are not well-defined by the Galerkin condition on the associated Krylov subspaces. In this paper, we derive a simple modification of the BCG algorithm, the Composite Step BCG (CSBCG) algorithm, which is able to compute all the well-defined BCG iterates stably, assuming that the underlying Lanczos process does not break down. The main idea is to skip over a step for which the BCG iterate is not defined.The work of this author was supported by the Office of Naval Research under contract N00014-89J-1440.The work of this author was supported by the Office of Naval Research under contracts N00014-90J-1695 and N00014-92J-1890, the Department of Energy under contract DE-FG03-87ER25307, the National Science Foundation under contracts ASC 90-03002 and 92-01266, and the Army Research Office under contract DAAL03-91-G-0150. Part of this work was completed during a visit to the Computer Science Dept., The Chinese University of Hong Kong.     

Transpose-free formulations of Lanczos-type methods for nonsymmetric linear systems

We present a transpose-free version of the nonsymmetric scaled Lanczos procedure. It generates the same tridiagonal matrix as the classical algorithm, using two matrix–vector products per iteration without accessing A^T. We apply this algorithm to obtain a transpose-free version of the Quasi-minimal residual method of Freund and Nachtigal [15] (without look-ahead), which requires three matrix–vector products per iteration. We also present a related transpose-free version of the bi-conjugate gradients algorithm. This revised version was published online in June 2006 with corrections to the Cover Date.     

An extension of the conjugate residual method to nonsymmetric linear systems

The Conjugate Gradient (CG) method and the Conjugate Residual (CR) method are Krylov subspace methods for solving symmetric (positive definite) linear systems. To solve nonsymmetric linear systems, the Bi-Conjugate Gradient (Bi-CG) method has been proposed as an extension of CG. Bi-CG has attractive short-term recurrences, and it is the basis for the successful variants such as Bi-CGSTAB. In this paper, we extend CR to nonsymmetric linear systems with the aim of finding an alternative basic solver. Numerical experiments show that the resulting algorithm with short-term recurrences often gives smoother convergence behavior than Bi-CG. Hence, it may take the place of Bi-CG for the successful variants.     

A conjugate gradient algorithm for sparse linear inequalities

This paper presents a conjugate gradient method for solving systems of linear inequalities. The method is of dual optimization type and consists of two phases which can be implemented in a common framework. Phase 1 either finds the minimum-norm solution of the system or detects the inconsistency of the system. In the latter event, the method proceeds to Phase 2 in which an approximate least-squares solution to the system is obtained. The method is particularly suitable to large scale problems because it preserves the sparsity structure of the problem. Its efficiency is shown by computational comparisons with an SOR type method.     

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.     

A minimum residual algorithm for solving linear systems

A minimum residual algorithm for solving a large linear system (I+S)x=b, with b∈ℂ ⁿ and S∈ℂ ^n×n being readily invertible, is proposed. For this purpose Krylov subspaces are generated by applying S and S ^-1 cyclically. The iteration can be executed with every linear system once the coefficient matrix has been split into the sum of two readily invertible matrices. In case S is a translation and a rotation of a Hermitian matrix, a five term recurrence is devised. In memory of Germund Dahlquist (1925–2005).AMS subject classification (2000) 65F10     

A flexible CMRH algorithm for nonsymmetric linear systems

A flexible version of the CMRH algorithm is presented that allows varying preconditioning at every step of the algorithm. A consequence of the flexibility of this new variant is that any iterative methods can be incorporated as a preconditioner in the inner steps. Theoretical results that relate the residual norm of the new algorithm and the flexible GMRES, the new algorithm with CMRH itself, are given. Numerical experiments are carried out to illustrate the effectiveness of the proposed algorithm in comparison with the standard CMRH algorithm, ILU-preconditioned CMRH variants and the flexible GMRES algorithm.     

Application of the Lanczos algorithm for solving the linear systems that occur in continuation problems

We study the Lanczos method for solving symmetric linear systems with multiple right‐hand sides. First, we propose a numerical method of implementing the Lanczos method, which can provide all approximations to the solution vectors of the remaining linear systems. We also seek possible application of this algorithm for solving the linear systems that occur in continuation problems. Sample numerical results are reported. Copyright © 2002 John Wiley & Sons, Ltd.     

An interior point method for quadratic programs based on conjugate projected gradients

We propose an interior point method for large-scale convex quadratic programming where no assumptions are made about the sparsity structure of the quadratic coefficient matrixQ. The interior point method we describe is a doubly iterative algorithm that invokes aconjugate projected gradient procedure to obtain the search direction. The effect is thatQ appears in a conjugate direction routine rather than in a matrix factorization. By doing this, the matrices to be factored have the same nonzero structure as those in linear programming. Further, one variant of this method istheoretically convergent with onlyone matrix factorization throughout the procedure.     

An improved three-term conjugate gradient algorithm for solving unconstrained optimization problems

In this article, we present an improved three-term conjugate gradient algorithm for large-scale unconstrained optimization. The search directions in the developed algorithm are proved to satisfy an approximate secant equation as well as the Dai-Liao’s conjugacy condition. With the standard Wolfe line search and the restart strategy, global convergence of the algorithm is established under mild conditions. By implementing the algorithm to solve 75 benchmark test problems with dimensions from 1000 to 10,000, the obtained numerical results indicate that the algorithm outperforms the state-of-the-art algorithms available in the literature. It costs less CPU time and smaller number of iterations in solving the large-scale unconstrained optimization.     

On modification of certain methods of the conjugate direction type for solving systems of linear algebraic equations

A modification of certain well-known methods of the conjugate direction type is proposed and examined. The modified methods are more stable with respect to the accumulation of round-off errors. Moreover, these methods are applicable for solving ill-conditioned systems of linear algebraic equations that, in particular, arise as approximations of ill-posed problems. Numerical results illustrating the advantages of the proposed modification are presented.     

On modification of certain methods of the conjugate direction type for solving rectangular systems of linear algebraic equations

The use of modifications of certain well-known methods of the conjugate direction type for solving systems of linear algebraic equations with rectangular matrices is examined. The modified methods are shown to be superior to the original versions with respect to the round-off accumulation; the advantage is especially large for ill-conditioned matrices. Examples are given of the efficient use of the modified methods for solving certain fairly large ill-conditioned problems.     

Weighted FOM and GMRES for solving nonsymmetric linear systems

This paper presents two new methods called WFOM and WGMRES, which are variants of FOM and GMRES, for solving large and sparse nonsymmetric linear systems. To accelerate the convergence, these new methods use a different inner product instead of the Euclidean one. Furthermore, at each restart, a different inner product is chosen. The weighted Arnoldi process is introduced for implementing these methods. After describing the weighted methods, we give the relations that link them to FOM and GMRES. Experimental results are presented to show the good performances of the new methods compared to FOM(m) and GMRES(m). This revised version was published online in August 2006 with corrections to the Cover Date.     

A strongly polynomial algorithm for solving two-sided linear systems in max-algebra

An algorithm for solving m×n systems of (max,+)-linear equations is presented. The systems have variables on both sides of the equations. After O(m⁴n⁴) iterations the algorithm either finds a solution of the system or finds out that no solution exists. Each iteration needs O(mn) operations so that the complexity of the presented algorithm is O(m⁵n⁵).     

On the convergence behavior of the restarted GMRES algorithm for solving nonsymmetric linear systems

The solution of nonsymmetric systems of linear equations continues to be a difficult problem. A main algorithm for solving nonsymmetric problems is restarted GMRES. The algorithm is based on restarting full GMRES every s iterations, for some integer s>0. This paper considers the impact of the restart frequency s on the convergence and work requirements of the method. It is shown that a good choice of this parameter can lead to reduced solution time, while an improper choice may hinder or preclude convergence. An adaptive procedure is also presented for determining automatically when to restart. The results of numerical experiments are presented.     

BiCR variants of the hybrid BiCG methods for solving linear systems with nonsymmetric matrices

We propose Bi-Conjugate Residual (BiCR) variants of the hybrid Bi-Conjugate Gradient (BiCG) methods (referred to as the hybrid BiCR variants) for solving linear systems with nonsymmetric coefficient matrices. The recurrence formulas used to update an approximation and a residual vector are the same as those used in the corresponding hybrid BiCG method, but the recurrence coefficients are different; they are determined so as to compute the coefficients of the residual polynomial of BiCR. From our experience it appears that the hybrid BiCR variants often converge faster than their BiCG counterpart. Numerical experiments show that our proposed hybrid BiCR variants are more effective and less affected by rounding errors. The factor in the loss of convergence speed is analyzed to clarify the difference of the convergence between our proposed hybrid BiCR variants and the hybrid BiCG methods.     

Analysis of the finite precision bi-conjugate gradient algorithm for nonsymmetric linear systems

In this paper we analyze the bi-conjugate gradient algorithm in finite precision arithmetic, and suggest reasons for its often observed robustness. By using a tridiagonal structure, which is preserved by the finite precision bi-conjugate gradient iteration, we are able to bound its residual norm by a minimum polynomial of a perturbed matrix (i.e. the residual norm of the exact GMRES applied to a perturbed matrix) multiplied by an amplification factor. This shows that occurrence of near-breakdowns or loss of biorthogonality does not necessarily deter convergence of the residuals provided that the amplification factor remains bounded. Numerical examples are given to gain insights into these bounds.

     

Extending the eigCG algorithm to nonsymmetric Lanczos for linear systems with multiple right‐hand sides

The technique that was used to build the eigCG algorithm for sparse symmetric linear systems is extended to the nonsymmetric case using the BiCG algorithm. We show that, similar to the symmetric case, we can build an algorithm that is capable of computing a few smallest magnitude eigenvalues and their corresponding left and right eigenvectors of a nonsymmetric matrix using only a small window of the BiCG residuals while simultaneously solving a linear system with that matrix. For a system with multiple right‐hand sides, we give an algorithm that computes incrementally more eigenvalues while solving the first few systems and then uses the computed eigenvectors to deflate BiCGStab for the remaining systems. Our experiments on various test problems, including Lattice QCD, show the remarkable ability of eigBiCG to compute spectral approximations with accuracy comparable with that of the unrestarted, nonsymmetric Lanczos. Furthermore, our incremental eigBiCG followed by appropriately restarted and deflated BiCGStab provides a competitive method for systems with multiple right‐hand sides. Copyright © 2013 John Wiley & Sons, Ltd.     

A parallel algorithm for solving Toeplitz linear systems

Numerical methods of solution are considered for systems which are Toeplitz and symmetric. In our case, the coefficient matrix is essentially tridiagonal and sparse. There are two distinct approaches to be considered each of which is efficient in its own way. Here we will combine the two approaches which will allow application of the cyclic reduction method to coefficient matrices of more general forms. The convergence of the approximations to the exact solution will also be examined. Solving linear systems by the adapted cyclic reduction method can be parallel processed.