Iterative methods for cyclically reduced nonselfadjoint linear systems

Elman, Howard C.; Golub, Gene H.

doi:10.1090/S0025-5718-1990-1011442-X

Iterative methods for cyclically reduced nonselfadjoint linear systems
HTML articles powered by AMS MathViewer

by Howard C. Elman and Gene H. Golub PDF

Math. Comp. 54 (1990), 671-700 Request permission

Abstract:

We study iterative methods for solving linear systems of the type arising from two-cyclic discretizations of non-self-adjoint two-dimensional elliptic partial differential equations. A prototype is the convection-diffusion equation. The methods consist of applying one step of cyclic reduction, resulting in a "reduced system" of half the order of the original discrete problem, combined with a reordering and a block iterative technique for solving the reduced system. For constant-coefficient problems, we present analytic bounds on the spectral radii of the iteration matrices in terms of cell Reynolds numbers that show the methods to be rapidly convergent. In addition, we describe numerical experiments that supplement the analysis and that indicate that the methods compare favorably with methods for solving the "unreduced" system.

References

Eugen F. F. Botta and Arthur E. P. Veldman, On local relaxation methods and their application to convection-diffusion equations, J. Comput. Phys. 48 (1982), no. 1, 127–149. MR 680848, DOI 10.1016/0021-9991(82)90039-0
Tony F. Chan and Howard C. Elman, Fourier analysis of iterative methods for elliptic problems, SIAM Rev. 31 (1989), no. 1, 20–49. MR 986481, DOI 10.1137/1031002

Conjugate gradient methods for partial differential equations

R. C. Y. Chin and Thomas A. Manteuffel, An analysis of block successive overrelaxation for a class of matrices with complex spectra, SIAM J. Numer. Anal. 25 (1988), no. 3, 564–585. MR 942208, DOI 10.1137/0725036
Raymond C. Y. Chin, Thomas A. Manteuffel, and John de Pillis, ADI as a preconditioning for solving the convection-diffusion equation, SIAM J. Sci. Statist. Comput. 5 (1984), no. 2, 281–299. MR 740847, DOI 10.1137/0905020
A. R. Curtis, On a property of some test equations for finite difference or finite element methods, IMA J. Numer. Anal. 1 (1981), no. 3, 369–375. MR 641316, DOI 10.1093/imanum/1.3.369

Block-preconditioned conjugate-gradientlike methods for numerical reservoir simulation

3

Iterative methods for large, sparse, nonsymmetric systems of linear equations

Matrix eigensystem routines

EISPACK guide extension

Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
L. A. Hageman, Franklin T. Luk, and David M. Young, On the equivalence of certain iterative acceleration methods, SIAM J. Numer. Anal. 17 (1980), no. 6, 852–873. MR 595449, DOI 10.1137/0717071
Louis A. Hageman and David M. Young, Applied iterative methods, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1981. MR 630192
G. W. Hedstrom and Albert Osterheld, The effect of cell Reynolds number on the computation of a boundary layer, J. Comput. Phys. 37 (1980), no. 3, 399–421. MR 588260, DOI 10.1016/0021-9991(80)90045-5
Seymour V. Parter, On estimating the “rates of convergence” of iterative methods for elliptic difference equations, Trans. Amer. Math. Soc. 114 (1965), 320–354. MR 181121, DOI 10.1090/S0002-9947-1965-0181121-1
S. Parter, The use of linear graphs in Gauss elimination, SIAM Rev. 3 (1961), 119–130. MR 143349, DOI 10.1137/1003021
Seymour V. Parter and J. W. T. Youngs, The symmetrization of matrices by diagonal matrices, J. Math. Anal. Appl. 4 (1962), 102–110. MR 148675, DOI 10.1016/0022-247X(62)90032-X

PCGPAK User’s Guide

A. Segal, Aspects of numerical methods for elliptic singular perturbation problems, SIAM J. Sci. Statist. Comput. 3 (1982), no. 3, 327–349. MR 667831, DOI 10.1137/0903020

Block SOR applied to the cyclicallyreduced equations as an efficient solution technique for convection-diffusion equations

Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR 0158502
David M. Young, Iterative solution of large linear systems, Academic Press, New York-London, 1971. MR 0305568