Iterative methods for cyclically reduced nonselfadjoint linear systems. II

Authors:
Howard C. Elman and Gene H. Golub

Journal:
Math. Comp. **56** (1991), 215-242

MSC:
Primary 65F10; Secondary 65N22

MathSciNet review:
1052093

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We perform an analytic and experimental study of line iterative methods for solving linear systems arising from finite difference discretizations of non-self-adjoint elliptic partial differential equations on two-dimensional domains. The methods consist of performing one step of cyclic reduction, followed by solution of the resulting reduced system by line relaxation. We augment previous analyses of one-line methods, and we derive a new convergence analysis for two-line methods, showing that both classes of methods are highly effective for solving the convection-diffusion equation. In addition, we compare the experimental performance of several variants of these methods, and we show that the methods can be implemented efficiently on parallel architectures.

**[1]**Loyce M. Adams and Harry F. Jordan,*Is SOR color-blind?*, SIAM J. Sci. Statist. Comput.**7**(1986), no. 2, 490–506. MR**833917**, 10.1137/0907033**[2]**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**, 10.1137/0725036**[3]**J. J. Dongarra, J. R. Bunch, C. B. Moler, and G. W. Stewart,*LINPACK users' guide*, SIAM, Philadelphia, PA, 1979.**[4]**Howard C. Elman and Gene H. Golub,*Iterative methods for cyclically reduced nonselfadjoint linear systems*, Math. Comp.**54**(1990), no. 190, 671–700. MR**1011442**, 10.1090/S0025-5718-1990-1011442-X**[5]**Gene H. Golub and Richard S. Varga,*Chebyshev semi-iterative methods, successive over-relaxation iterative methods, and second order Richardson iterative methods. I*, Numer. Math.**3**(1961), 147–156. MR**0145678****[6]**Louis A. Hageman and Richard S. Varga,*Block iterative methods for cyclically reduced matrix equations*, Numer. Math.**6**(1964), 106–119. MR**0166912****[7]**Louis A. Hageman and David M. Young,*Applied iterative methods*, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1981. Computer Science and Applied Mathematics. MR**630192****[8]**R. S. Garbow, J. M. Boyle, J. J. Dongarra, and C. B. Moler,*Matrix eigensystem routines: EISPACK guide extension*, Springer-Verlag, New York, 1972.**[9]**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****[10]**MACSYMA Reference Manual, Laboratory for Computer Science, MIT, 1977.**[11]**T. A. Manteuffel,*Optimal parameters for linear second-degree stationary iterative methods*, SIAM J. Numer. Anal.**19**(1982), no. 4, 833–839. MR**664888**, 10.1137/0719058**[12]**Seymour V. Parter,*Iterative methods for elliptic problems and the discovery of “𝑞”*, SIAM Rev.**28**(1986), no. 2, 153–175. MR**839821**, 10.1137/1028049**[13]**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**0181121**, 10.1090/S0002-9947-1965-0181121-1**[14]**Seymour V. Parter,*On “two-line” iterative methods for the Laplace and biharmonic difference equations*, Numer. Math.**1**(1959), 240–252. MR**0128626****[15]**Seymour V. Parter and Michael Steuerwalt,*Block iterative methods for elliptic and parabolic difference equations*, SIAM J. Numer. Anal.**19**(1982), no. 6, 1173–1195. MR**679658**, 10.1137/0719084**[16]**PCGPAK User's Guide, Version 1.04, Scientific Computing Associates, New Haven, CT, 1987.**[17]**A. Segal,*Aspects of numerical methods for elliptic singular perturbation problems*, SIAM J. Sci. Statist. Comput.**3**(1982), no. 3, 327–349. MR**667831**, 10.1137/0903020**[18]**Richard S. Varga,*Matrix iterative analysis*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1962. MR**0158502****[19]**David M. Young,*Iterative solution of large linear systems*, Academic Press, New York-London, 1971. MR**0305568**

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

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

Additional Information

DOI:
http://dx.doi.org/10.1090/S0025-5718-1991-1052093-1

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

Article copyright:
© Copyright 1991
American Mathematical Society