## 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
R. Chandra, - 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
S. C. Eisenstat, H. C. Elman, and M. H. Schultz, - 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 - 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
M. C. Thompson, J. H. Ferziger, and G. H. Golub, - 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**

*Conjugate gradient methods for partial differential equations*, Ph.D. Thesis, Department of Computer Science, Yale University, 1978.

*Block-preconditioned conjugate-gradientlike methods for numerical reservoir simulation*, SPE Reservoir Engineering

**3**(1988), 307-312. H. C. Elman,

*Iterative methods for large, sparse, nonsymmetric systems of linear equations*, Ph.D. Thesis, Department of Computer Science, Yale University, 1982. R. S. Garbow, J. M. Boyle, J. J. Dongarra, and C. B. Moler,

*Matrix eigensystem routines*:

*EISPACK guide extension*, Springer-Verlag, New York, 1972.

*PCGPAK User’s Guide*, Version 1.04, Scientific Computing Associates, New Haven, CT, 1987.

*Block SOR applied to the cyclicallyreduced equations as an efficient solution technique for convection-diffusion equations*, in Computational Techniques and Applications, CTAC-87 (John Noye and Clive Fletcher, eds.), North-Holland, New York, 1988, pp. 637-646.

## Additional Information

- © Copyright 1990 American Mathematical Society
- Journal: Math. Comp.
**54**(1990), 671-700 - MSC: Primary 65F10; Secondary 65N22
- DOI: https://doi.org/10.1090/S0025-5718-1990-1011442-X
- MathSciNet review: 1011442