Iterative methods for cyclically reduced nonselfadjoint linear systems

Authors:
Howard C. Elman and Gene H. Golub

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

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

**[1]**E. F. F. Botta and A. E. P. Veldman,*On local relaxation methods and their application to convection-diffusion equations*, J. Comput. Phys.**48**(1981), 127-149. MR**680848 (83m:76067)****[2]**T. F. Chan and H. C. Elman,*Fourier analysis of iterative methods for elliptic problems*, SIAM Rev.**31**(1989), 20-49. MR**986481 (90h:65162)****[3]**R. Chandra,*Conjugate gradient methods for partial differential equations*, Ph.D. Thesis, Department of Computer Science, Yale University, 1978.**[4]**R. C. Y. Chin and T. A. Manteuffel,*An analysis of block successive overrelaxation for a class of matrices with complex spectra*, SIAM J. Numer. Anal.**25**(1988), 564-585. MR**942208 (89e:65037)****[5]**R. C. Y. Chin, T. A. Manteuffel, and J. de Pillis,*ADI as a preconditioning for solving the convection-diffusion equation*, SIAM J. Sci. Statist. Comput.**5**(1984), 281-299. MR**740847 (86g:65067)****[6]**A. R. Curtis,*On a property of some test equations for finite difference methods*, IMA J. Numer. Anal.**1**(1981), 369-375. MR**641316 (83a:65097)****[7]**S. C. Eisenstat, H. C. Elman, and M. H. Schultz,*Block-preconditioned conjugate-gradientlike methods for numerical reservoir simulation*, SPE Reservoir Engineering**3**(1988), 307-312.**[8]**H. C. Elman,*Iterative methods for large, sparse, nonsymmetric systems of linear equations*, Ph.D. Thesis, Department of Computer Science, Yale University, 1982.**[9]**R. S. Garbow, J. M. Boyle, J. J. Dongarra, and C. B. Moler,*Matrix eigensystem routines*:*EISPACK guide extension*, Springer-Verlag, New York, 1972.**[10]**G. H. Golub and C. F. van Loan,*Matrix computations*, The Johns Hopkins University Press, Baltimore, MD, 1983. MR**733103 (85h:65063)****[11]**L. A. Hageman, F. T. Luk, and D. M. Young,*On the equivalence of certain acceleration methods*, SIAM J. Numer. Anal.**17**(1980), 852-873. MR**595449 (82c:65018)****[12]**L. A. Hageman and D. M. Young,*Applied iterative methods*, Academic Press, New York, 1981. MR**630192 (83c:65064)****[13]**G. W. Hedstrom and A. Osterheld,*The effect of cell Reynolds number on the computation of a boundary layer*, J. Comput. Phys.**37**(1980), 399-421. MR**588260 (82a:76023)****[14]**S. V. Parter,*On estimating the "rates of convergence" of iterative methods for elliptic difference equations*, Trans. Amer. Math. Soc.**114**(1965), 320-354. MR**0181121 (31:5350)****[15]**-,*The use of linear graphs in Gaussian elimination*, SIAM Rev.**3**(1961), 119-130. MR**0143349 (26:908)****[16]**S. V. Parter and J. W. T. Youngs,*The symmetrization of matrices by diagonal matrices*, J. Math. Anal. Appl.**4**(1962), 102-110. MR**0148675 (26:6182)****[17]***PCGPAK User's Guide*, Version 1.04, Scientific Computing Associates, New Haven, CT, 1987.**[18]**A. Segal,*Aspects of numerical methods for elliptic singular perturbation problems*, SIAM J. Sci. Statist. Comput.**3**(1982), 327-349. MR**667831 (83j:65085)****[19]**M. C. Thompson, J. H. Ferziger, and G. H. Golub,*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.**[20]**R. S. Varga,*Matrix iterative analysis*, Prentice-Hall, Englewood Cliffs, N. J., 1962. MR**0158502 (28:1725)****[21]**D. M. Young,*Iterative solution of large linear systems*, Academic Press, New York, 1971. MR**0305568 (46:4698)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F10,
65N22

Retrieve articles in all journals with MSC: 65F10, 65N22

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1990-1011442-X

Keywords:
Linear systems,
reduced system,
iterative methods,
convection-diffusion,
non-self-adjoint

Article copyright:
© Copyright 1990
American Mathematical Society