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.

**[1]**M. D. Bakes,*An alternative method of solution of certain tri-diagonal systems of linear equations*, Comput. J.**7**(1964), 135–136. MR**0182130**, https://doi.org/10.1093/comjnl/7.2.135**[2]**Erwin H. Bareiss,*Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices*, Numer. Math.**13**(1969), 404–424. MR**0255027**, https://doi.org/10.1007/BF02163269**[3]**Friedrich L. Bauer,*Ein direktes Iterationsverfahren zur Hurwitz-Zerlegung eines Polynoms*, Arch. Elek. Übertr.**9**(1955), 285–290 (German). MR**0076447****[4]**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****[5]**O. Buneman,*A Compact Non-Iterative Poisson Solver*, Rep. SUIPR-294, Inst. Plasma Research, Stanford University, 1969.**[6]**O. Buneman,*Inversion of the Helmholtz (or Laplace-Poisson) Operator in Slab Geometry*, Rep. SUIPR-467, Inst. Plasma Research, Stanford University, 1972.**[7]**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**0287717**, https://doi.org/10.1137/0707049**[8]**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**0292316**, https://doi.org/10.1137/0708066**[9]**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.**[10]**D. J. Evans,*An algorithm for the solution of certain tridiagonal systems of linear equations*, Comput. J.**15**(1972), 356–359. MR**0323085**, https://doi.org/10.1093/comjnl/15.4.356**[11]**D. J. Evans and C. V. D. Forrington,*Note on the solution of certain tri-diagonal systems of linear equations*, Comput. J.**5**(1962/1963), 327–328. MR**0156454**, https://doi.org/10.1093/comjnl/5.4.327**[12]**George E. Forsythe and Cleve B. Moler,*Computer solution of linear algebraic systems*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR**0219223****[13]**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.**[14]**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.**[15]**R. W. Hockney,*A fast direct solution of Poisson’s equation using Fourier analysis*, J. Assoc. Comput. Mach.**12**(1965), 95–113. MR**0213048**, https://doi.org/10.1145/321250.321259**[16]**R. W. Hockney, "The potential calculation and some applications,"*Methods in Computational Physics*. Vol. 9, Academic Press, New York, 1970.**[17]**Alston S. Householder,*The theory of matrices in numerical analysis*, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1964. MR**0175290****[18]**M. Malcolm & J. Palmer,*A Fast Method for Solving a Class of Tri-Diagonal Linear Systems*, Computer Science Report 323, Stanford University, 1972.**[19]**W. Proskurowski & O. B. Widlund. (To appear.)**[20]**Frigyes Riesz and Béla Sz.-Nagy,*Functional analysis*, Frederick Ungar Publishing Co., New York, 1955. Translated by Leo F. Boron. MR**0071727****[21]**J. Rissanen and L. Barbosa,*Properties of infinite covariance matrices and stability of optimum predictors*, Information Sci.**1**(1968/1969), 221–236. MR**0243711****[22]**Donald J. Rose,*An algorithm for solving a special class of tridiagonal systems of linear equations*, Comm. ACM**12**(1969), 234–236. MR**0279985**, https://doi.org/10.1145/362912.362940**[23]**Gilbert Strang,*Implicit difference methods for initial-boundary value problems*, J. Math. Anal. Appl.**16**(1966), 188–198. MR**0205496**, https://doi.org/10.1016/0022-247X(66)90196-X**[24]**Vidar Thomée,*Elliptic difference operators and Dirichlet’s problem*, Contributions to Differential Equations**3**(1964), 301–324. MR**0163444****[25]**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.**[26]***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****[27]**G. Wilson,*Factorization of the covariance generating function of a pure moving average process*, SIAM J. Numer. Anal.**6**(1969), 1–7. MR**0253561**, https://doi.org/10.1137/0706001

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

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

Additional Information

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

Article copyright:
© Copyright 1974
American Mathematical Society