Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On Fourier-Toeplitz methods for separable elliptic problems

Authors: D. Fischer, G. Golub, O. Hald, C. Leiva and O. Widlund
Journal: Math. Comp. 28 (1974), 349-368
MSC: Primary 65F05; Secondary 65N20
MathSciNet review: 0415995
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 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
  • Erwin H. Bareiss, Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices, Numer. Math. 13 (1969), 404–424. MR 255027, DOI
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • Gilbert Strang, Implicit difference methods for initial-boundary value problems, J. Math. Anal. Appl. 16 (1966), 188–198. MR 205496, DOI
  • 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, Springer-Verlag, New York-Heidelberg, 1971. Linear algebra; Compiled by J. H. Wilkinson and C. Reinsch; Die Grundlehren der Mathematischen Wissenschaften, Band 186. 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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F05, 65N20

Retrieve articles in all journals with MSC: 65F05, 65N20

Additional Information

Article copyright: © Copyright 1974 American Mathematical Society