Iterative methods for cyclically reduced nonselfadjoint linear systems. II

Elman, Howard C.; Golub, Gene H.

doi:10.1090/S0025-5718-1991-1052093-1

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

by Howard C. Elman and Gene H. Golub PDF

Math. Comp. 56 (1991), 215-242 Request permission

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

Loyce M. Adams and Harry F. Jordan, Is SOR color-blind?, SIAM J. Sci. Statist. Comput. 7 (1986), no. 2, 490–506. MR 833917, DOI 10.1137/0907033
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

LINPACK users’ guide

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, DOI 10.1090/S0025-5718-1990-1011442-X
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 145678, DOI 10.1007/BF01386013
Louis A. Hageman and Richard S. Varga, Block iterative methods for cyclically reduced matrix equations, Numer. Math. 6 (1964), 106–119. MR 166912, DOI 10.1007/BF01386061
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

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
T. A. Manteuffel, Optimal parameters for linear second-degree stationary iterative methods, SIAM J. Numer. Anal. 19 (1982), no. 4, 833–839. MR 664888, DOI 10.1137/0719058
Seymour V. Parter, Iterative methods for elliptic problems and the discovery of “$q$”, SIAM Rev. 28 (1986), no. 2, 153–175. MR 839821, DOI 10.1137/1028049
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
Seymour V. Parter, On “two-line” iterative methods for the Laplace and biharmonic difference equations, Numer. Math. 1 (1959), 240–252. MR 128626, DOI 10.1007/BF01386388
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, DOI 10.1137/0719084
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
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