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

DOI:
https://doi.org/10.1090/S0025-5718-1974-0415995-2

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.

- 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 https://doi.org/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 https://doi.org/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, - 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 https://doi.org/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 https://doi.org/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," - D. J. Evans,
*An algorithm for the solution of certain tridiagonal systems of linear equations*, Comput. J.**15**(1972), 356–359. MR**323085**, DOI https://doi.org/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 https://doi.org/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," - 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 https://doi.org/10.1145/321250.321259
R. W. Hockney, "The potential calculation and some applications," - 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, - 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 https://doi.org/10.1016/s0020-0255%2869%2980009-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 https://doi.org/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 https://doi.org/10.1016/0022-247X%2866%2990196-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," *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 https://doi.org/10.1137/0706001

*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.

*J. Sound Vib.*, v. 12, 1970, pp. 315-337.

*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.

*Methods in Computational Physics*. Vol. 9, Academic Press, New York, 1970.

*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.)

*Sparse Matrices and Their Applications*, edited by D. J. Rose and R. A. Willoughby, Plenum Press, New York, 1972.

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