On Fourier-Toeplitz methods for separable elliptic problems
HTML articles powered by AMS MathViewer
- by D. Fischer, G. Golub, O. Hald, C. Leiva and O. Widlund PDF
- Math. Comp. 28 (1974), 349-368 Request permission
Abstract:
Some very fast numerical methods have been developed in recent years for the solution of elliptic differential equations which allow for separation of variables. In this paper, a Fourier-Toeplitz method is developed as an alternative to the well-known methods of Hockney and Buneman. It is based on the fast Fourier transform and Toeplitz factorizations. The use of Toeplitz factorizations combined with the Sherman-Morrison formula is also systematically explored for linear systems of algebraic equations with band matrices of Toeplitz, or almost Toeplitz form. Finally, results of numerical experiments are described.References
- M. D. Bakes, An alternative method of solution of certain tri-diagonal systems of linear equations, Comput. J. 7 (1964), 135–136. MR 182130, DOI 10.1093/comjnl/7.2.135
- Erwin H. Bareiss, Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices, Numer. Math. 13 (1969), 404–424. MR 255027, DOI 10.1007/BF02163269
- Friedrich L. Bauer, Ein direktes Iterationsverfahren zur Hurwitz-Zerlegung eines Polynoms, Arch. Elek. Übertr. 9 (1955), 285–290 (German). MR 76447
- Friedrich L. Bauer, Beiträge zur Entwicklung numerischer Verfahren für programmgesteuerte Rechenanlagen. II. Direkte Faktorisierung eines Polynoms, Bayer. Akad. Wiss. Math.-Nat. Kl. S.-B. 1956 (1956), 163–203 (1957) (German). MR 0089498 O. Buneman, A Compact Non-Iterative Poisson Solver, Rep. SUIPR-294, Inst. Plasma Research, Stanford University, 1969. O. Buneman, Inversion of the Helmholtz (or Laplace-Poisson) Operator in Slab Geometry, Rep. SUIPR-467, Inst. Plasma Research, Stanford University, 1972.
- B. L. Buzbee, G. H. Golub, and C. W. Nielson, On direct methods for solving Poisson’s equations, SIAM J. Numer. Anal. 7 (1970), 627–656. MR 287717, DOI 10.1137/0707049
- B. L. Buzbee, F. W. Dorr, J. A. George, and G. H. Golub, The direct solution of the discrete Poisson equation on irregular regions, SIAM J. Numer. Anal. 8 (1971), 722–736. MR 292316, DOI 10.1137/0708066 J. W. Cooley, P. A. W. Lewis & P. D. Welch, "The fast Fourier transform algorithm: Programming consideration in the calculation of sine, cosine and Laplace transform," J. Sound Vib., v. 12, 1970, pp. 315-337.
- D. J. Evans, An algorithm for the solution of certain tridiagonal systems of linear equations, Comput. J. 15 (1972), 356–359. MR 323085, DOI 10.1093/comjnl/15.4.356
- D. J. Evans and C. V. D. Forrington, Note on the solution of certain tri-diagonal systems of linear equations, Comput. J. 5 (1962/63), 327–328. MR 156454, DOI 10.1093/comjnl/5.4.327
- George E. Forsythe and Cleve B. Moler, Computer solution of linear algebraic systems, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0219223 J. A. George, "Block elimination of finite element systems of equations," Sparse Matrices and Their Applications, edited by D. J. Rose and R. A. Willoughby, Plenum Press, New York, 1972. J. A. George, The Use of Direct Methods for the Solution of the Discrete Poisson Equation on Non-Rectangular Regions, Computer Science Report 159, Stanford University, 1970.
- R. W. Hockney, A fast direct solution of Poisson’s equation using Fourier analysis, J. Assoc. Comput. Mach. 12 (1965), 95–113. MR 213048, DOI 10.1145/321250.321259 R. W. Hockney, "The potential calculation and some applications," Methods in Computational Physics. Vol. 9, Academic Press, New York, 1970.
- Alston S. Householder, The theory of matrices in numerical analysis, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1964. MR 0175290 M. Malcolm & J. Palmer, A Fast Method for Solving a Class of Tri-Diagonal Linear Systems, Computer Science Report 323, Stanford University, 1972. W. Proskurowski & O. B. Widlund. (To appear.)
- Frigyes Riesz and Béla Sz.-Nagy, Functional analysis, Frederick Ungar Publishing Co., New York, 1955. Translated by Leo F. Boron. MR 0071727
- J. Rissanen and L. Barbosa, Properties of infinite covariance matrices and stability of optimum predictors, Information Sci. 1 (1968/1969), 221–236. MR 0243711, DOI 10.1016/s0020-0255(69)80009-5
- Donald J. Rose, An algorithm for solving a special class of tridiagonal systems of linear equations, Comm. ACM 12 (1969), 234–236. MR 0279985, DOI 10.1145/362912.362940
- Gilbert Strang, Implicit difference methods for initial-boundary value problems, J. Math. Anal. Appl. 16 (1966), 188–198. MR 205496, DOI 10.1016/0022-247X(66)90196-X
- Vidar Thomée, Elliptic difference operators and Dirichlet’s problem, Contributions to Differential Equations 3 (1964), 301–324. MR 163444 O. B. Widlund, "On the use of fast methods for separable finite difference equations for the solution of general elliptic problems," Sparse Matrices and Their Applications, edited by D. J. Rose and R. A. Willoughby, Plenum Press, New York, 1972.
- Handbook for automatic computation. Vol. II, Die Grundlehren der mathematischen Wissenschaften, Band 186, Springer-Verlag, New York-Heidelberg, 1971. Linear algebra; Compiled by J. H. Wilkinson and C. Reinsch. MR 0461856
- G. Wilson, Factorization of the covariance generating function of a pure moving average process, SIAM J. Numer. Anal. 6 (1969), 1–7. MR 253561, DOI 10.1137/0706001
Additional Information
- © Copyright 1974 American Mathematical Society
- Journal: Math. Comp. 28 (1974), 349-368
- MSC: Primary 65F05; Secondary 65N20
- DOI: https://doi.org/10.1090/S0025-5718-1974-0415995-2
- MathSciNet review: 0415995