Abstract
Classical wavefront preconditioned iteration methods for difference matrices on a rectangular or on a rectangular parallelepipedal domain use wavefronts based on diagonal (line or plane, respectively) orderings of the meshpoint. Since such wavefronts do not have constant widths, they cannot be implemented efficiently on parallel computers.
We discuss various methods to get wavefronts with constant width for difference matrices for second order elliptic problems. In particular, we discuss their applications for the nine-point (2D) and 15-point (3D) difference approximations for the Laplacian, which are fourth order accurate for proper choices of the coefficients. It turns out that we can easily get preconditioning methods with wavefronts in the form of vertical or horizontal lines both in 2D and 3D, which have condition numberO(h −1), but for general three space dimensional problems no simple ordering leading to constant plane wavefronts seems to exist in general, for which the corresponding preconditioner has such a small condition number. A crucial property we make use of in the methods is the spectral equivalence between the nine-point and the standard five-point difference matrices and between the 15-point and the standard seven-point difference matrices in two and three space dimensions, respectively.
The methods use only nearest neighbor connections and can therefore be implemented efficiently not only on shared memory computers but also on distributed memory computer architectures, such as mesh-connected computer architectures.
Zusammenfassung
Klassische Wellenfront-vorkonditionierte iterative Methoden für Differenzmatrizen verwenden Wellenfronten, die auf diagonalen (Linien- oder Flächen-) Ordnungen der Gitterpunkte basieren. Da solche Wellenfronten keine konstante Breite haben, ist es nicht möglich, sie effizient auf Parallelrechner-Architekturen auszuführen.
Wir diskutieren verschiedene Methoden, wie man Wellenfronten mit konstanter Breite für elliptische Probleme zweiter Ordnung erhalten kann. Insbesondere diskutieren wir die Anwendung dieser Methoden für neun- (2D) und fünfzehnpunktige (3D) Differenzapproximationen des Laplaceoperators, die für geeignete Wahl der Koeffizienten von vierter Ordnung sind. Wir erhalten vorkonditionierte Methoden mit Wellenfronten als vertikale oder horizontale Linien sowohl in 2D als auch in 3D, die die KonditionszahlO(h −1) haben.
Die Methoden benutzen nur Verbindungen zu benachbarten Knoten. Infolgedessen können sie nicht nur auf Rechner-Architekturen mit geteiltem Speicher, sondern auch auf verteilten Systemen, Z.B. vernetzten Parallelrechner-Architekturen, effizient ausgeführt werden.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ashcraft, C. C., Grimes, R.G.: On vectorizing incomplete factorization and SSOR preconditioners,SIAM J. Sci. Stat. Comput.,9 (1988), 122–151.
Axelsson, O.: A generalized SSOR method,BIT,12 (1972) 443–467.
Axelsson, O.: On iterative solution of elliptic difference equations on a mesh-connected array of processors,Int. J. High Speed Computing,1 (1989), 165–183.
Axelsson, O.: Condition number-estimates for elliptic difference problems with anisotropy, Equadiff 7, Teubner-Texte zur Mathematik, Band 118, (Teubner, Leizig, 1990), 218–224.
Axelsson, O.: Bounds of eigenvalues of preconditioned matrices,Proceedings Copper Mountain Conference on Iterative Methods, April 1–5, 1990.
Axelsson, O.: A multilevel solution method for nine-point difference approximations, inParallel Supercomputing: Methods, Algorithms and Applications, Chapter 13, p. 191–205. Edited by Graham F. Carey, Wiley, 1989.
Axelsson, O.: A mixed variable finite element method for the efficient solution of nonlinear diffusion and potential flow equations, in D. Braess, W. Hackbush and U. Trottenberg, eds.,Advances in Multi-grid Methods (Vieweg, Braunschweig, 1985), 1–11.
Axelsson, O., Barker, V. A.:Finite Element Solution of Boundary Value Problems. (Academic Press, Orlando, FL 1984).
Axelsson, O., Carey, G., Lindskog, G.: On a class of preconditioned iterative methods on parallel computers,Int. J. Numer. Meth. Eng.,27 (1989), 637–654.
Axelsson, O., Eijkhout, V.: Vectorizable preconditioners for elliptic difference equations in three space dimensions,J. Comp. Appl. Math.,27 (1989), 299–321.
Axelsson, O., Eijkhout, V.: Analysis of a recursive 5-point/9-point factorization method, in O. Axelsson and L. Yu. Kalotitina, eds.Preconditioned Conjugate Gradient Methods, Lecture Notes in Mathematics #1457 (Springer-Verlag, Berlin Heidelberg, 1990).
Axelsson, O., Gustafsson, I.: An efficient finite element method for nonlinear diffusion problems, Report 84.06R, Department of Computer Sciences, Chalmers University of Technology, Goteborg, Sweden, 1984.
Axelsson, O., Kolotilina, L.: Monotonicity and discretization error estimates,SIAM J. Numer. Analysis, 27 (1990), 1591–1611.
Axelsson, O., Maubach, J.: On the updating and assembly of the Hessian matrix in finite element methods, inComputer Methods in Applied Mechanics and Engineering,71 (1988), 41–67.
Eisenstat, S. C.: Efficient implementations of a class of preconditioned conjugate gradient methods,SIAM J. Sci. Stat. Comput.,2 (1981), 1–4.
Gustafsson, I.: A class of 1st order factorization methods,BIT 18 (1978), 142–156.
Niethammer, W.: Relaxation bei komplexen Matrizen,Math. Z.,86 (1964), 34–40.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Axelsson, O., Lindskog, G. Constant wavefront iteration methods for nine- and 15-point difference matrices. Computing 46, 233–252 (1991). https://doi.org/10.1007/BF02238300
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02238300