Search

One of the most powerful iterative schemes for solving symmetric, positive definite linear systems is the conjugate gradient algorithm of Hestenes and Stiefel [J. Res. Nat. Bur. Standards, 49 (1952), pp. 409-435], especially when it is combined with preconditioning (cf. [P. Concus, G.H. Golub, and D.P. O'Leary, in Proceedings of the Symposium on Sparse Matrix Computations, Argonne National Laboratory, 1975, Academic, New York, 1976]). In many applications, the solution of a sequence of equations with the same coefficient matrix is required. We propose an approach based on a combination of the conjugate gradient method with Chebyshev filtering polynomials, applied only to a part of the spectrum of the coefficient matrix, as preconditioners that target some specific convergence properties of the conjugate gradient method. We show that our preconditioner puts a large number of eigenvalues near one and do not degrade the distribution of the smallest ones. This procedure enables us to construct a lower dimensional Krylov basis that is very rich with respect to the smallest eigenvalues and associated eigenvectors. A major benefit of our method is that this information can then be exploited in a straightforward way to solve sequences of systems with little extra work. We illustrate the performance of our method through numerical experiments on a set of linear systems. [ABSTRACT FROM AUTHOR]

For the iterative solution of saddle point problems, a nonsymmetric preconditioner is studied which, with respect to the upper-left block of the system matrix, can be seen as a variant of SSOR. An idealized situation where SSOR is taken with respect to the skew-symmetric part plus the diagonal part of the upper-left block is analyzed in detail. Since action of the preconditioner involves solution of a Schur complement system, an inexact form of the preconditioner can be of interest. This results in an inner-outer iterative process. Numerical experiments with solution of linearized Navier-Stokes equations demonstrate the efficiency of the new preconditioner, especially when the upper-left block is far from symmetric. [ABSTRACT FROM AUTHOR]

In this paper we consider the solution of linear systems of saddle point type by preconditioned Krylov subspace methods. A preconditioning strategy based on the symmetric/skew-symmetric splitting of the coefficient matrix is proposed, and some useful properties of the preconditioned matrix are established. The potential of this approach is illustrated by numerical experiments with matrices from various application areas. [ABSTRACT FROM AUTHOR]

A parallel algorithm is proposed for the solution of narrow banded non-symmetric linear systems. The linear system is partitioned into blocks of rows with a small number of unknowns common to multiple blocks. Our technique yields a reduced system defined only on these common unknowns which can then be solved by a direct or iterative method. A projection based extension to this approach is also proposed for computing the reduced system implicitly, which gives rise to an inner–outer iteration method. In addition, the product of a vector with the reduced system matrix can be computed efficiently on a multiprocessor by concurrent projections onto subspaces of block rows. Scalable implementations of the algorithm can be devized for hierarchical parallel architectures by exploiting the two-level parallelism inherent in the method. Our experiments indicate that the proposed algorithm is a robust and competitive alternative to existing methods, particularly for difficult problems with strong indefinite symmetric part. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We analyze the preconditioned Chebyshev iteration in which at each step the linear system involving the preconditioner is solved inexactly by an inner iteration. We allow the tolerance used in the inner iteration to decrease from one outer iteration to the next. When the tolerance converges to zero, the asymptotic convergence rate is the same as for the exact method. Motivated by this result, we seek the sequence of tolerance values that yields the lowest cost to achieve a specified accuracy. We find that among all sequences of slowly varying tolerances, a constant one is optimal. Numerical calculations that verify our results are presented. Asymptotic methods, such as the W.K.B. method for linear recurrence equations, are used with an estimate of the accuracy of the asymptotic result. [ABSTRACT FROM AUTHOR]