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.*, v. 7, 1964, pp. 135-136. MR**31**#6353. MR**0182130 (31:6353)****[2]**E. H. Bareiss, "Numerical solution of linear equations with Toeplitz and vector Toeplitz matrices,"*Numer. Math.*, v. 13, 1969, pp. 404-424. MR**40**#8234. MR**0255027 (40:8234)****[3]**F. L. Bauer, "Ein direktes Iterationsverfahren zur Hurwitz-Zerlegung eines Polynoms,"*Arch. Elec. Ubertr.*, v. 9, 1955, pp. 285-290. MR**17**, 900. MR**0076447 (17:900e)****[4]**F. 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.*, v. 1956, pp. 163-203. MR**19**, 686. MR**0089498 (19:686a)****[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 & C. W. Nielson, "On direct methods for solving Poisson's equation,"*SIAM J. Numer. Anal.*, v. 7, 1970, pp. 627-656. MR**44**#4920. MR**0287717 (44:4920)****[8]**B. L. Buzbee, F. W. Dorr, J. A. George & G. H. Golub, "The direct solution of the discrete Poisson equation on irregular regions,"*J. SIAM Numer. Anal.*, v. 8, 1971, pp. 722-736. MR**45**#1403. MR**0292316 (45:1403)****[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 tri-diagonal systems of linear equations,"*Comput. J.*, v. 15, 1972, pp. 356-359. MR**0323085 (48:1443)****[11]**D. J. Evans & C. V. D. Forrington, "Note on the solution of certain tri-diagonal systems of linear equations,"*Comput. J.*, v. 5, 1962/63, pp. 327-328. MR**27**#6377. MR**0156454 (27:6377)****[12]**G. E. Forsythe & C. B. Moler,*Computer Solution of Linear Algebraic Systems*, Prentice-Hall, Englewood Cliffs, N.J., 1967. MR**36**#2306. MR**0219223 (36:2306)****[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.*, v. 12, 1965, pp. 95-113. MR**35**#3913. MR**0213048 (35:3913)****[16]**R. W. Hockney, "The potential calculation and some applications,"*Methods in Computational Physics*. Vol. 9, Academic Press, New York, 1970.**[17]**A. S. Householder,*The Theory of Matrices in Numerical Analysis*, Blaisdell, New York, 1964. MR**30**#5475. MR**0175290 (30:5475)****[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]**F. Riesz & B. Sz.-Nagy,*Leçons d'analyse fonctionnelle*, 2nd ed., Akad. Kiadó, Budapest, 1953; English transl.,*Functional Analysis*, Ungar, New York, 1955. MR**15**, 132;**17**, 175. MR**0071727 (17:175i)****[21]**J. Rissanen & L. Barbosa, "Properties of infinite covariance matrices and stability of optimum predictors,"*Information Science*, v. 1, 1968/69, pp. 221-236. MR**39**#5032. MR**0243711 (39:5032)****[22]**D. J. Rose, "An algorithm for solving a special class of tri-diagonal systems of linear equations,"*Comm. ACM*, v. 12, 1969, pp. 234-236. MR**43**#5706. MR**0279985 (43:5706)****[23]**G. Strang, "Implicit difference methods for initial-boundary value problems,"*J. Math. Anal. Appl.*, v. 16, 1966, pp. 188-198. MR**34**#5323. MR**0205496 (34:5323)****[24]**V. Thomée, "Elliptic difference operators and Dirichlet's problem,"*Contributions to Differential Equations*, v. 3, 1964, pp. 301-324. MR**29**#746. MR**0163444 (29:746)****[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]**J. H. Wilkinson & C. Reinsch, "Linear algebra,"*Handbook for Automatic Computation*, Springer-Verlag, Berlin and New York, 1971. MR**0461856 (57:1840)****[27]**G. Wilson, "Factorization of the covariance generating function of a pure moving average process,"*SIAM J. Numer. Anal.*, v. 6, 1969, pp. 1-7. MR**40**#6775. MR**0253561 (40:6775)**

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