Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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

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.

References [Enhancements On Off] (What's this?)

  • [1] L. M. Adams and H. F. Jordan, Is SOR color blind?, SIAM J. Sci. Statist. Comput. 7 (1986), 490-506. MR 833917 (87i:65039)
  • [2] 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)
  • [3] J. J. Dongarra, J. R. Bunch, C. B. Moler, and G. W. Stewart, LINPACK users' guide, SIAM, Philadelphia, PA, 1979.
  • [4] H. C. Elman and G. H. Golub, Iterative methods for cyclically reduced non-self-adjoint linear systems, Math. Comp. 54 (1990), 671-700. MR 1011442 (91b:65036)
  • [5] G. H. Golub and R. S. Varga, Chebyshev semi-iterative methods, successive overtaxation iterative methods, and second order Richardson iterative methods, Numer. Math. 3 (1961), 147-156. MR 0145678 (26:3207)
  • [6] L. A. Hageman and R. S. Varga, Block iterative methods for cyclically reduced matrix equations, Numer. Math. 6 (1964), 106-119. MR 0166912 (29:4185)
  • [7] L. A. Hageman and D. M. Young, Applied iterative methods, Academic Press, San Diego, 1981. MR 630192 (83c:65064)
  • [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] G. H. Golub and C. F. Van Loan, Matrix computations, The Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103 (85h:65063)
  • [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), 833-839. MR 664888 (83f:65047)
  • [12] S. V. Parter, Iterative methods for elliptic problems and the discovery of "q", SIAM Rev. 28 (1986), 153-175. MR 839821 (87m:65166)
  • [13] -, 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)
  • [14] -, On "two-line" iterative methods for the Laplace and biharmonic difference equations, Numer. Math. 1 (1959), 240-252. MR 0128626 (23:B1664)
  • [15] S. V. Parter and M. Steuerwalt, Block iterative methods for elliptic and parabolic difference equations, SIAM J. Numer. Anal. 19 1982), 1173-1195. MR 679658 (84b:65033)
  • [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), 327-349. MR 667831 (83j:65085)
  • [18] R. S. Varga, Matrix iterative analysis, Prentice-Hall, Englewood Cliffs, NJ, 1962. MR 0158502 (28:1725)
  • [19] D. M. Young, Iterative solution of large linear systems, Academic Press, New York, 1971. MR 0305568 (46:4698)

Similar Articles

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

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

Additional Information

Keywords: Linear systems, reduced system, iterative methods, convection-diffusion, non-self-adjoint
Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society