On FourierToeplitz methods for separable elliptic problems
Authors:
D. Fischer, G. Golub, O. Hald, C. Leiva and O. Widlund
Journal:
Math. Comp. 28 (1974), 349368
MSC:
Primary 65F05; Secondary 65N20
MathSciNet review:
0415995
Fulltext 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 FourierToeplitz method is developed as an alternative to the wellknown methods of Hockney and Buneman. It is based on the fast Fourier transform and Toeplitz factorizations. The use of Toeplitz factorizations combined with the ShermanMorrison 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 tridiagonal
systems of linear equations, Comput. J. 7 (1964),
135–136. MR 0182130
(31 #6353)
 [2]
Erwin
H. Bareiss, Numerical solution of linear equations with Toeplitz
and vector Toeplitz matrices, Numer. Math. 13 (1969),
404–424. MR 0255027
(40 #8234)
 [3]
Friedrich
L. Bauer, Ein direktes Iterationsverfahren zur HurwitzZerlegung
eines Polynoms, Arch. Elek. Übertr. 9 (1955),
285–290 (German). MR 0076447
(17,900e)
 [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
(19,686a)
 [5]
O. Buneman, A Compact NonIterative Poisson Solver, Rep. SUIPR294, Inst. Plasma Research, Stanford University, 1969.
 [6]
O. Buneman, Inversion of the Helmholtz (or LaplacePoisson) Operator in Slab Geometry, Rep. SUIPR467, 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
(44 #4920)
 [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
(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. 315337.
 [10]
D.
J. Evans, An algorithm for the solution of certain tridiagonal
systems of linear equations, Comput. J. 15 (1972),
356–359. MR 0323085
(48 #1443)
 [11]
D.
J. Evans and C.
V. D. Forrington, Note on the solution of certain tridiagonal
systems of linear equations, Comput. J. 5
(1962/1963), 327–328. MR 0156454
(27 #6377)
 [12]
George
E. Forsythe and Cleve
B. Moler, Computer solution of linear algebraic systems,
PrenticeHall, Inc., Englewood Cliffs, N.J., 1967. 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 NonRectangular 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
(35 #3913)
 [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 YorkTorontoLondon, 1964. MR 0175290
(30 #5475)
 [18]
M. Malcolm & J. Palmer, A Fast Method for Solving a Class of TriDiagonal 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
(17,175i)
 [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
(39 #5032)
 [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
(43 #5706)
 [23]
Gilbert
Strang, Implicit difference methods for initialboundary value
problems, J. Math. Anal. Appl. 16 (1966),
188–198. MR 0205496
(34 #5323)
 [24]
Vidar
Thomée, Elliptic difference operators and Dirichlet’s
problem, Contributions to Differential Equations 3
(1964), 301–324. 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]
Handbook for automatic computation. Vol. II, SpringerVerlag, New
YorkHeidelberg, 1971. Linear algebra; Compiled by J. H. Wilkinson and C.
Reinsch; Die Grundlehren der Mathematischen Wissenschaften, Band 186. MR 0461856
(57 #1840)
 [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
(40 #6775)
 [1]
 M. D. Bakes, "An alternative method of solution of certain tridiagonal systems of linear equations," Comput. J., v. 7, 1964, pp. 135136. 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. 404424. MR 40 #8234. MR 0255027 (40:8234)
 [3]
 F. L. Bauer, "Ein direktes Iterationsverfahren zur HurwitzZerlegung eines Polynoms," Arch. Elec. Ubertr., v. 9, 1955, pp. 285290. 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. 163203. MR 19, 686. MR 0089498 (19:686a)
 [5]
 O. Buneman, A Compact NonIterative Poisson Solver, Rep. SUIPR294, Inst. Plasma Research, Stanford University, 1969.
 [6]
 O. Buneman, Inversion of the Helmholtz (or LaplacePoisson) Operator in Slab Geometry, Rep. SUIPR467, 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. 627656. 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. 722736. 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. 315337.
 [10]
 D. J. Evans, "An algorithm for the solution of certain tridiagonal systems of linear equations," Comput. J., v. 15, 1972, pp. 356359. MR 0323085 (48:1443)
 [11]
 D. J. Evans & C. V. D. Forrington, "Note on the solution of certain tridiagonal systems of linear equations," Comput. J., v. 5, 1962/63, pp. 327328. MR 27 #6377. MR 0156454 (27:6377)
 [12]
 G. E. Forsythe & C. B. Moler, Computer Solution of Linear Algebraic Systems, PrenticeHall, 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 NonRectangular 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. 95113. 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 TriDiagonal 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. 221236. MR 39 #5032. MR 0243711 (39:5032)
 [22]
 D. J. Rose, "An algorithm for solving a special class of tridiagonal systems of linear equations," Comm. ACM, v. 12, 1969, pp. 234236. MR 43 #5706. MR 0279985 (43:5706)
 [23]
 G. Strang, "Implicit difference methods for initialboundary value problems," J. Math. Anal. Appl., v. 16, 1966, pp. 188198. 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. 301324. 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, SpringerVerlag, 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. 17. MR 40 #6775. MR 0253561 (40:6775)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F05,
65N20
Retrieve articles in all journals
with MSC:
65F05,
65N20
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197404159952
PII:
S 00255718(1974)04159952
Article copyright:
© Copyright 1974
American Mathematical Society
