On nonlinear generalized conjugate gradient methods

Summary. The Generalized Conjugate Gradient method (see [1]) is an iterative method for nonsymmetric linear systems. We obtain generalizations of this method for nonlinear systems with nonsymmetric Jacobians. We prove global convergence results. Received April 29, 1992 / Revised version received November 18, 1993     

A COCR method for solving complex symmetric linear systems

The Conjugate Orthogonal Conjugate Gradient (COCG) method has been recognized as an attractive Lanczos-type Krylov subspace method for solving complex symmetric linear systems; however, it sometimes shows irregular convergence behavior in practical applications. In the present paper, we propose a Conjugate A$A$-Orthogonal Conjugate Residual (COCR) method, which can be regarded as an extension of the Conjugate Residual (CR) method. Numerical examples show that COCR often gives smoother convergence behavior than COCG.     

Connections between the PCG method applied to systems with Red/Black form and its reduced system

This paper is concerned with the (preconditioned) conjugate gradient method for solving systems of linear algebraic equationsAx=b withA having Red/Black form. The connections between the Conjugate Gradient (CG) scheme applied toAx=b and its two reduced systems are explored under certain conditions.     

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.     

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.     

Conjugate Direction Methods and Polarity for Quadratic Hypersurfaces

We use some results from polarity theory to recast several geometric properties of Conjugate Gradient-based methods, for the solution of nonsingular symmetric linear systems. This approach allows us to pursue three main theoretical objectives. First, we can provide a novel geometric perspective on the generation of conjugate directions, in the context of positive definite systems. Second, we can extend the above geometric perspective to treat the generation of conjugate directions for handling indefinite linear systems. Third, by exploiting the geometric insight suggested by polarity theory, we can easily study the possible degeneracy (pivot breakdown) of Conjugate Gradient-based methods on indefinite linear systems. In particular, we prove that the degeneracy of the standard Conjugate Gradient on nonsingular indefinite linear systems can occur only once in the execution of the Conjugate Gradient.     

The Bound-Constrained Conjugate Gradient Method for Non-negative Matrices

Existing conjugate gradient (CG)-based methods for convex quadratic programs with bound constraints require many iterations for solving elastic contact problems. These algorithms are too cautious in expanding the active set and are hampered by frequent restarting of the CG iteration. We propose a new algorithm called the Bound-Constrained Conjugate Gradient method (BCCG). It combines the CG method with an active-set strategy, which truncates variables crossing their bounds and continues (using the Polak–Ribière formula) instead of restarting CG. We provide a case with n=3 that demonstrates that this method may fail on general cases, but we conjecture that it always works if the system matrix A is non-negative. Numerical results demonstrate the effectiveness of the method for large-scale elastic contact problems.     

ChebStaBlkCG: A block variant of ChebFilterCG

The behavior of ChebFilterCG (an algorithm that combines the Chebyshev filter and Conjugate Gradient) applied to systems with unfavorable eigenvalue distribution is examined. To improve the convergence, a hybrid approach combining a stabilized version of the block conjugated gradient with Chebyshev polynomials as preconditioners (ChebStaBlkCG) is proposed. The performance of ChebStaBlkCG is illustrated and validated on a set of linear systems. It is shown how ChebStaBlkCG can be used to accelerate the block Cimmino method and to solve linear systems with multiple right‐hand sides.     

Convergence of CG and GMRES on a tridiagonal Toeplitz linear system

The Conjugate Gradient method (CG), the Minimal Residual method (MINRES), or more generally, the Generalized Minimal Residual method (GMRES) are widely used to solve a linear system Ax=b. The choice of a method depends on A’s symmetry property and/or definiteness), and MINRES is really just a special case of GMRES. This paper establishes error bounds on and sometimes exact expressions for residuals of CG, MINRES, and GMRES on solving a tridiagonal Toeplitz linear system, where A is Hermitian or just normal. These expressions and bounds are in terms of the three parameters that define A and Chebyshev polynomials of the first or second kind. AMS subject classification (2000)  65F10, 65N22     

A new family of global methods for linear systems with multiple right-hand sides

The global bi-conjugate gradient (Gl-BCG) method is an attractive matrix Krylov subspace method for solving nonsymmetric linear systems with multiple right-hand sides, but it often show irregular convergence behavior in many applications. In this paper, we present a new family of global A-biorthogonal methods by using short two-term recurrences and formal orthogonal polynomials, which contain the global bi-conjugate residual (Gl-BCR) algorithm and its improved version. Finally, numerical experiments illustrate that the proposed methods are highly competitive and often superior to originals.     

Block Conjugate Gradient Iteration for Fourier-Galerkin Homogenization of Periodic Media

The Fourier-Galerkin method is considered here for the solution of the unit cell problem that describes the homogenized properties of periodic materials in the scalar elliptic setting. The method is based on a Galerkin approximation with trigonometric polynomials and leads to linear systems suitable for iterative solvers. In [1], Zeman et al show the effectiveness of Conjugate gradients (CG) which is compared here with its block version (BCG). We show that the latter version outperforms the CG especially for anisotropic materials with non-symmetric distribution of material properties. (© 2015 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Iterative Methods for Queuing Systems with Batch Arrivals and Negative Customers

In this paper, we are interested in solving the stationary probability distributions of Markovian queuing systems having batch arrivals and negative customers by using the Preconditioned Conjugate Gradient Squared (PCGS) method. The preconditioner is constructed by exploiting the near-Toeplitz structure of the generator matrix of the system. We proved that under some mild conditions the preconditioned linear systems have singular values clustered around one when the size of the queue tends to infinity. Numerical results indicated that the convergence rate of the proposed method is very fast.     

TIME-EXTRAPOLATION ALGORITHM （TEA） FOR LINEAR PARABOLIC PROBLEMS

The fast solutions of Crank-Nicolson scheme on quasi-uniform mesh for parabolic prob- lems are discussed. First, to decrease regularity requirements of solutions, some new error estimates are proved. Second, we analyze the two characteristics of parabolic discrete scheme, and find that the efficiency of Multigrid Method （MG） is greatly reduced. Nu- merical experiments compare the efficiency of Direct Conjugate Gradient Method （DCG） and Extrapolation Cascadic Multigrid Method （EXCMG）. Last, we propose a Time- Extrapolation Algorithm （TEA）, which takes a linear combination of previous several level solutions as good initial values to accelerate the rate of convergence. Some typical extrapolation formulas are compared numerically. And we find that under certain accuracy requirement, the CG iteration count for the 3-order and 7-level extrapolation formula is about 1/3 of that of DCG＇s. Since the TEA algorithm is independent of the space dimension, it is still valid for quasi-uniform meshes. As only the finest grid is needed, the proposed method is regarded very effective for nonlinear parabolic problems.     

A new family of global methods for linear systems with multiple right-hand sides

The global bi-conjugate gradient (Gl-BCG) method is an attractive matrix Krylov subspace method for solving nonsymmetric linear systems with multiple right-hand sides, but it often show irregular convergence behavior in many applications. In this paper, we present a new family of global $A$-biorthogonal methods by using short two-term recurrences and formal orthogonal polynomials, which contain the global bi-conjugate residual (Gl-BCR) algorithm and its improved version. Finally, numerical experiments illustrate that the proposed methods are highly competitive and often superior to originals.     

Variants of the groupwise update strategy for short-recurrence Krylov subspace methods

Krylov subspace methods often use short-recurrences for updating approximations and the corresponding residuals. In the bi-conjugate gradient (Bi-CG) type methods, rounding errors arising from the matrix–vector multiplications used in the recursion formulas influence the convergence speed and the maximum attainable accuracy of the approximate solutions. The strategy of a groupwise update has been proposed for improving the convergence of the Bi-CG type methods in finite-precision arithmetic. In the present paper, we analyze the influence of rounding errors on the convergence properties when using alternative recursion formulas, such as those used in the bi-conjugate residual (Bi-CR) method, which are different from those used in the Bi-CG type methods. We also propose variants of a groupwise update strategy for improving the convergence speed and the accuracy of the approximate solutions. Numerical experiments demonstrate the effectiveness of the proposed method.     

A nonmonotone truncated Newton–Krylov method exploiting negative curvature directions, for large scale unconstrained optimization

We propose a new truncated Newton method for large scale unconstrained optimization, where a Conjugate Gradient (CG)-based technique is adopted to solve Newton’s equation. In the current iteration, the Krylov method computes a pair of search directions: the first approximates the Newton step of the quadratic convex model, while the second is a suitable negative curvature direction. A test based on the quadratic model of the objective function is used to select the most promising between the two search directions. Both the latter selection rule and the CG stopping criterion for approximately solving Newton’s equation, strongly rely on conjugacy conditions. An appropriate linesearch technique is adopted for each search direction: a nonmonotone stabilization is used with the approximate Newton step, while an Armijo type linesearch is used for the negative curvature direction. The proposed algorithm is both globally and superlinearly convergent to stationary points satisfying second order necessary conditions. We carry out a significant numerical experience in order to test our proposal.     

Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems

Summary. We present generalizations of the nonsymmetric Levinson and Schur algorithms for non-Hermitian Toeplitz matrices with some singular or ill-conditioned leading principal submatrices. The underlying recurrences allow us to go from any pair of successive well-conditioned leading principal submatrices to any such pair of larger order. If the look-ahead step size between these pairs is bounded, our generalized Levinson and Schur recurrences require $ operations, and the Schur recurrences can be combined with recursive doubling so that an $ algorithm results. The overhead (in operations and storage) of look-ahead steps is very small. There are various options for applying these algorithms to solving linear systems with Toeplitz matrix. Received July 26, 1993     

Numerical solution of the generalized Stokes problem for the flow in a channel

In this article we introduce the separation of variables in the two-dimensional generalized Stokes problem. −νΔu + αu + inverted delta p = f, for the flow in a channel. Also for the first time, we discuss the implementation of the Incremental Unknowns Method with a data structure of Compressed Column Storage. Two examples of application of the Incremental Unknowns method for this problem are presented in which we compare the CPU times of three methods: Conjugate Gradient (CG), Incremental Unknowns (IU), and Uzawa Algorithm (Uzawa). © 1997 John Wiley & Sons, Inc.     

Steepest Descent, CG, and Iterative Regularization of Ill-Posed Problems

The state of the art iterative method for solving large linear systems is the conjugate gradient (CG) algorithm. Theoretical convergence analysis suggests that CG converges more rapidly than steepest descent. This paper argues that steepest descent may be an attractive alternative to CG when solving linear systems arising from the discretization of ill-posed problems. Specifically, it is shown that, for ill-posed problems, steepest descent has a more stable convergence behavior than CG, which may be explained by the fact that the filter factors for steepest descent behave much less erratically than those for CG. Moreover, it is shown that, with proper preconditioning, the convergence rate of steepest descent is competitive with that of CG.This revised version was published online in October 2005 with corrections to the Cover Date.     

GPBi‐CGstab(L): A Lanczos‐type product method unifying Bi‐CGstab(L) and GPBi‐CG

Lanczos‐type product methods (LTPMs), in which the residuals are defined by the product of stabilizing polynomials and the Bi‐CG residuals, are effective iterative solvers for large sparse nonsymmetric linear systems. Bi‐CGstab(L) and GPBi‐CG are popular LTPMs and can be viewed as two different generalizations of other typical methods, such as CGS, Bi‐CGSTAB, and Bi‐CGStab2. Bi‐CGstab(L) uses stabilizing polynomials of degree L, while GPBi‐CG uses polynomials given by a three‐term recurrence (or equivalently, a coupled two‐term recurrence) modeled after the Lanczos residual polynomials. Therefore, Bi‐CGstab(L) and GPBi‐CG have different aspects of generalization as a framework of LTPMs. In the present paper, we propose novel stabilizing polynomials, which combine the above two types of polynomials. The resulting method is referred to as GPBi‐CGstab(L). Numerical experiments demonstrate that our presented method is more effective than conventional LTPMs.