On the numerical solution of Helmholtz's equation by the capacitance matrix method
Authors:
Wlodzimierz Proskurowski and Olof Widlund
Journal:
Math. Comp. 30 (1976), 433468
MSC:
Primary 65N05; Secondary 35J05
MathSciNet review:
0421102
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: In recent years the usefulness of fast Laplace solvers has been extended to problems on arbitrary regions in the plane by the development of capacitance matrix methods. The solution of the Dirichlet and Neumann problems for Helmholtz's equation is considered. It is shown, that by an appropriate choice of the fast solver, the capacitance matrix can be generated quite inexpensively. An analogy between capacitance matrix methods and classical potential theory for the solution of Laplace's equation is explored. This analogy suggests a modification of the method in the Dirichlet case. This new formulation leads to wellconditioned capacitance matrix equations which can be solved quite efficiently by the conjugate gradient method. A highly accurate solution can, therefore, be obtained at an expense which grows no faster than that for a fast Laplace solver on a rectangle when the mesh size is decreased.
 [1]
Edward
Angel and Richard
Bellman, Dynamic programming and partial differential
equations, Academic Press, New York, 1972. Mathematics in Science and
Engineering, Vol. 88. MR 0359368
(50 #11822)
 [2]
Richard
Bartels and James
W. Daniel, A conjugate gradient approach to nonlinear elliptic
boundary value problems in irregular regions, Conference on the
Numerical Solution of Differential Equations (Univ. Dundee, Dundee, 1973),
Springer, Berlin, 1974, pp. 1–11. Lecture Notes in Math., Vol.
363. MR
0440965 (55 #13833)
 [3]
J.
H. Bramble and B.
E. Hubbard, A theorem on error estimation for finite difference
analogues of the Dirichlet problem for elliptic equations,
Contributions to Differential Equations 2 (1963),
319–340. MR 0152134
(27 #2114)
 [4]
J.
H. Bramble and B.
E. Hubbard, Approximation of derivatives by finite difference
methods in elliptic boundary value problems, Contributions to
Differential Equations 3 (1964), 399–410. MR 0166935
(29 #4208)
 [5]
O. BUNEMAN, A Compact NonIterative Poisson Solver, Report SUIPR294, Inst. Plasma Research, Stanford University, 1969.
 [6]
B.
L. Buzbee and Fred
W. Dorr, The direct solution of the biharmonic equation on
rectangular regions and the Poisson equation on irregular regions,
SIAM J. Numer. Anal. 11 (1974), 753–763. MR 0362944
(50 #15382)
 [7]
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)
 [8]
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)
 [9]
J.
Albrecht and L.
Collatz (eds.), Numerische Behandlung von Differentialgleichungen.
Band 3, Internationale Schriftenreihe zur Numerischen Mathematik
[International Series of Numerical Mathematics], vol. 56,
Birkhäuser Verlag, Basel, 1981 (German). MR 784038
(86b:65003)
 [10]
Paul
Concus and Gene
H. Golub, Use of fast direct methods for the efficient numerical
solution of nonseparable elliptic equations, SIAM J. Numer. Anal.
10 (1973), 1103–1120. MR 0341890
(49 #6636)
 [11]
J. W. COOLEY, P. A. W. LEWIS & P. D. WELCH, "The fast Fourier transform algorithm: Programming considerations in the calculation of sine, cosine and Laplace transform," J. Sound Vib., v. 12, 1970, pp. 315337.
 [12]
R.
Courant and D.
Hilbert, Methods of mathematical physics. Vol. I, Interscience
Publishers, Inc., New York, N.Y., 1953. MR 0065391
(16,426a)
 [13]
James
W. Daniel, The conjugate gradient method for linear and nonlinear
operator equations, SIAM J. Numer. Anal. 4 (1967),
10–26. MR
0217987 (36 #1076)
 [14]
Fred
W. Dorr, The direct solution of the discrete Poisson equation on a
rectangle., SIAM Rev. 12 (1970), 248–263. MR 0266447
(42 #1353)
 [15]
D.
Fischer, G.
Golub, O.
Hald, C.
Leiva, and O.
Widlund, On FourierToeplitz methods for
separable elliptic problems, Math. Comp. 28 (1974), 349–368.
MR
0415995 (54 #4072), http://dx.doi.org/10.1090/S00255718197404159952
 [16]
George
E. Forsythe and Wolfgang
R. Wasow, Finitedifference methods for partial differential
equations, Applied Mathematics Series, John Wiley & Sons Inc., New
York, 1960. MR
0130124 (23 #B3156)
 [17]
P.
R. Garabedian, Partial differential equations, John Wiley
& Sons Inc., New York, 1964. MR 0162045
(28 #5247)
 [18]
J. A. GEORGE, The Use of Direct Methods for the Solution of the Discrete Poisson Equation on NonRectangular Regions, Computer Science Department Report 159, Stanford University, 1970.
 [19]
G. H. GOLUB, "An Algorithm for the Discrete Biharmonic Equation," (Unpublished.)
 [20]
R.
M. Hayes, Iterative methods of solving linear problems on Hilbert
space, Contributions to the solution of systems of linear equations
and the determination of eigenvalues, National Bureau of Standards Applied
Mathematics Series No. 39, U. S. Government Printing Office, Washington, D.
C., 1954, pp. 71–103. MR 0066563
(16,597b)
 [21]
Magnus
R. Hestenes, The conjugategradient method for solving linear
systems, Proceedings of Symposia in Applied Mathematics. Vol. VI.
Numerical analysis, McGrawHill Book Company, Inc., New York, for the
American Mathematical Society, Providence, R. I., 1956,
pp. 83–102. MR 0084178
(18,824c)
 [22]
Magnus
R. Hestenes and Eduard
Stiefel, Methods of conjugate gradients for solving linear
systems, J. Research Nat. Bur. Standards 49 (1952),
409–436 (1953). MR 0060307
(15,651a)
 [23]
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)
 [24]
R. W. HOCKNEY, "Formation and stability of virtual electrodes in a cylinder," J. Appl. Phys., v. 39, 1968, pp. 41664170.
 [25]
R. W. HOCKNEY, The Potential Calculation and Some Applications, Methods in Computational Physics, vol. 9, Academic Press, New York, 1970.
 [26]
R. W. HOCKNEY, POT 4A Fast Direct Poisson Solver for the Rectangle Allowing Some Mixed Boundary Conditions and Internal Electrodes, IBM Research, R. C. 2870, 1970.
 [27]
R. W. HOCKNEY, Computers, Compilers and PoissonSolvers, Computer Science Department Report, Reading University, 1972.
 [28]
Alston
S. Householder, The theory of matrices in numerical analysis,
Blaisdell Publishing Co. Ginn and Co. New YorkTorontoLondon, 1964. MR 0175290
(30 #5475)
 [29]
A. JAMESON, Accelerated Iteration Schemes for Transonic Flow Calculations Using Fast Poisson Solvers, N. Y. U. ERDA report C00307782, 1975.
 [30]
W.
J. Kammerer and M.
Z. Nashed, On the convergence of the conjugate gradient method for
singular linear operator equations, SIAM J. Numer. Anal.
9 (1972), 165–181. MR 0319368
(47 #7912)
 [31]
Shmuel
Kaniel, Estimates for some computational
techniques in linear algebra, Math. Comp.
20 (1966),
369–378. MR 0234618
(38 #2934), http://dx.doi.org/10.1090/S00255718196602346184
 [32]
L.
V. Kantorovich and V.
I. Krylov, Approximate methods of higher analysis, Translated
from the 3rd Russian edition by C. D. Benster, Interscience Publishers,
Inc., New York, 1958. MR 0106537
(21 #5268)
 [33]
Cornelius
Lanczos, An iteration method for the solution of the eigenvalue
problem of linear differential and integral operators, J. Research
Nat. Bur. Standards 45 (1950), 255–282. MR 0042791
(13,163d)
 [34]
D. G. LUENBERGER, Introduction to Linear and Nonlinear Programming, AddisonWesley, Reading, Mass., 1973.
 [35]
E.
Dale Martin, A generalizedcapacitymatrix technique for computing
aerodynamic flows, Internat. J. Comput.\thinspace&\thinspace
Fluids 2 (1974), no. 1, 79–97. MR 0347233
(49 #11953)
 [36]
E. D. MARTIN, "Progress in application of direct elliptic solvers for transonic flow computations," Aeordynamics Analyses Requiring Advanced Computers, NASA SP347, 1975. (To appear.)
 [37]
E.
Dale Martin, A fast semidirect method for computing transonic
aerodynamic flows, AIAA J. 14 (1976), no. 7,
914–922. MR 0459290
(56 #17484)
 [38]
C.
C. Paige and M.
A. Saunders, Solutions of sparse indefinite systems of linear
equations, SIAM J. Numer. Anal. 12 (1975),
no. 4, 617–629. MR 0383715
(52 #4595)
 [39]
V. PEREYRA, W. PROSKUROWSKI & O. WIDLUND, "On a family of elliptic difference schemes suggested by HeinzOtto Kreiss." (To appear.)
 [40]
C. S. PESKIN, Personal communication.
 [41]
I.
G. Petrovskiĭ, Lekcii ob uravneniyah c častnymi
proizvodnymi, Gosudarstv. Izdat. Tehn.Teor. Lit., MoscowLeningrad,],
1950 (Russian). MR 0043322
(13,241f)
 [42]
A. SHIEH, Fast Poisson Solver on Nonrectangular Domains, Ph. D. Thesis, New York University, June 1976.
 [43]
Gilbert
Strang and George
J. Fix, An analysis of the finite element method,
PrenticeHall Inc., Englewood Cliffs, N. J., 1973. PrenticeHall Series in
Automatic Computation. MR 0443377
(56 #1747)
 [44]
Vidar
Thomée, On the convergence of difference quotients in
elliptic problems, Numerical Solution of Field Problems in Continuum
Physics (Proc. Sympos. Appl. Math., Durham, N.C., 1968), SIAMAMS Proc.,
Vol. II, Amer. Math. Soc., Providence, R. I., 1970,
pp. 186–200. MR 0260206
(41 #4834)
 [45]
Survey of numerical analysis, McGrawHill Book Co., Inc., New
York, 1962. MR
0135221 (24 #B1271)
 [46]
O. 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.
 [1]
 E. ANGEL & R. BELLMAN, Dynamic Programming and Parital Differential Equations, Math. in Sci. and Engineering, vol. 88, Academic Press, New York and London, 1972. MR 50 #11822. MR 0359368 (50:11822)
 [2]
 R. BARTELS & J. W. DANIEL, "A conjugate gradient approach to nonlinear elliptic boundary value problems in irregular regions," Conference on the Numerical Solution of Differential Equations (Dundee, July 1973), Lecture Notes in Math., vol. 363, SpringerVerlag, Berlin and New York, 1974, pp. 111. MR 0440965 (55:13833)
 [3]
 J. H. BRAMBLE & B. E. HUBBARD, "A theorem on error estimation for finite difference analogues of the Dirichlet problem for elliptic equations," Contributions to Differential Equations, v. 2, 1963, pp. 319340. MR 27 #2114. MR 0152134 (27:2114)
 [4]
 J. H. BRAMBLE & B. E. HUBBARD, "Approximation of derivatives by finite difference methods in elliptic boundary value problems," Contributions to Differential Equations, v. 3, 1964, pp. 399410. MR 29 #4208. MR 0166935 (29:4208)
 [5]
 O. BUNEMAN, A Compact NonIterative Poisson Solver, Report SUIPR294, Inst. Plasma Research, Stanford University, 1969.
 [6]
 B. L. BUZBEE & F. W. DORR, "The direct solution of the biharmonic equation on rectangular regions and the Poisson equation on irregular regions," SIAM J. Numer. Anal., v. 11, 1974, pp. 753763. MR 0362944 (50:15382)
 [7]
 B. L. BUZBEE, F. W. DORR, J. A. GEORGE & G. H. GOLUB, "The direct solution of the discrete Poisson equation on irregular regions," SIAM J. Numer. Anal., v. 8, 1971, pp. 722736. MR 45 #1403. MR 0292316 (45:1403)
 [8]
 B. L. BUZBEE, G. H. GOLUB & C. W. NIELSON, "On direct methods for solving Poisson's equations," SIAM J. Numer. Anal., v. 7, 1970, pp. 627656. MR 44 #4920. MR 0287717 (44:4920)
 [9]
 L. COLLATZ, The Numerical Treatment of Differential Equations, SpringerVerlag, Berlin and New York, 1966. MR 784038 (86b:65003)
 [10]
 P. CONCUS & G. H. GOLUB, "Use of fast direct methods for efficient numerical solution of nonseparable elliptic equations," SIAM J. Numer. Anal., v. 10, 1973, pp. 11031120. MR 49 #6636. MR 0341890 (49:6636)
 [11]
 J. W. COOLEY, P. A. W. LEWIS & P. D. WELCH, "The fast Fourier transform algorithm: Programming considerations in the calculation of sine, cosine and Laplace transform," J. Sound Vib., v. 12, 1970, pp. 315337.
 [12]
 R. COURANT & D. HILBERT, Methods of Mathematical Physics. Vol. I, Interscience, New York, 1953. MR 16, 426. MR 0065391 (16:426a)
 [13]
 J. W. DANIEL, "The conjugate gradient method for linear and nonlinear operator equations," SIAM J. Numer. Anal., v. 4, 1967, pp. 1026. MR 36 #1076. MR 0217987 (36:1076)
 [14]
 F. W. DORR, "The direct solution of the discrete Poisson equation on a rectangle," SIAM Rev., v. 12, 1970, pp. 248263. MR 42 #1353. MR 0266447 (42:1353)
 [15]
 D. FISCHER, G. GOLUB, O. HALD, C. LEIVA & O. WIDLUND, "On FourierToeplitz methods for separable elliptic problems," Math. Comp., v. 28, 1974, pp. 349368. MR 0415995 (54:4072)
 [16]
 G. E. FORSYTHE & W. R. WASOW, FiniteDifference Methods for Partial Differential Equations, Appl. Math. Ser., Wiley, New York, 1960. MR 23 #B3156. MR 0130124 (23:B3156)
 [17]
 P. R. GARABEDIAN, Partial Differential Equations, Wiley, New York, 1964. MR 28 #5247. MR 0162045 (28:5247)
 [18]
 J. A. GEORGE, The Use of Direct Methods for the Solution of the Discrete Poisson Equation on NonRectangular Regions, Computer Science Department Report 159, Stanford University, 1970.
 [19]
 G. H. GOLUB, "An Algorithm for the Discrete Biharmonic Equation," (Unpublished.)
 [20]
 R. M. HAYES, "Iterative methods of solving linear problems on Hilbert space," Contributions to the Solution of Systems of Linear Equations and the Determination of Eigenvalues, Nat. Bur. Standards Appl. Math. Ser., no. 39, U. S. Government Printing Office, Washington, D. C., 1954, pp. 71103. MR 16, 597. MR 0066563 (16:597b)
 [21]
 M. R. HESTENES, "The conjugate gradient method for solving linear systems," Proc. Sympos. Appl. Math., vol. 6, Numer. Anal., Amer. Math. Soc., Providence, R. I., 1956, pp. 83102. MR 18, 824. MR 0084178 (18:824c)
 [22]
 M. R. HESTENES & E. STIEFEL, "Methods of conjugate gradients for solving linear systems," J. Res. Nat. Bur. Standards, v. 49, 1952, pp. 409436. MR 15, 651. MR 0060307 (15:651a)
 [23]
 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)
 [24]
 R. W. HOCKNEY, "Formation and stability of virtual electrodes in a cylinder," J. Appl. Phys., v. 39, 1968, pp. 41664170.
 [25]
 R. W. HOCKNEY, The Potential Calculation and Some Applications, Methods in Computational Physics, vol. 9, Academic Press, New York, 1970.
 [26]
 R. W. HOCKNEY, POT 4A Fast Direct Poisson Solver for the Rectangle Allowing Some Mixed Boundary Conditions and Internal Electrodes, IBM Research, R. C. 2870, 1970.
 [27]
 R. W. HOCKNEY, Computers, Compilers and PoissonSolvers, Computer Science Department Report, Reading University, 1972.
 [28]
 A. S. HOUSEHOLDER, The Theory of Matrices in Numerical Analysis, Blaisdell, New York, 1964. MR 30 #5475. MR 0175290 (30:5475)
 [29]
 A. JAMESON, Accelerated Iteration Schemes for Transonic Flow Calculations Using Fast Poisson Solvers, N. Y. U. ERDA report C00307782, 1975.
 [30]
 W. J. KAMMERER & M. Z. NASHED, "On the convergence of the conjugate gradient method for singular operator equations," SIAM J. Numer. Anal., v. 9, 1972, pp. 165181. MR 0319368 (47:7912)
 [31]
 S. KANIEL, "Estimates for some computational techniques in linear algebra," Math. Comp., v. 20, 1966, pp. 369378. MR 38 #2934. MR 0234618 (38:2934)
 [32]
 L. V. KANTOROVIČ & V. I. KRYLOV, Approximate Methods of Higher Analysis, 3rd ed., GITTL, Moscow, 1950; English transl., Interscience, New York; Noordhoff, Groningen, 1958. MR 13, 77; 21 #5268. MR 0106537 (21:5268)
 [33]
 C. LANCZOS, "An iteration method for the solution of the eigenvalue problem of linear differential and integral operators," J. Res. Nat. Bur. Standards, v. 45, 1950, pp. 255282. MR 13, 163. MR 0042791 (13:163d)
 [34]
 D. G. LUENBERGER, Introduction to Linear and Nonlinear Programming, AddisonWesley, Reading, Mass., 1973.
 [35]
 E. D. MARTIN, "A generalizedcapacitymatrix technique for computing aerodynamic flows," Internat. J. Comput. & Fluids, v. 2, 1974, pp. 7997. MR 49 #11953. MR 0347233 (49:11953)
 [36]
 E. D. MARTIN, "Progress in application of direct elliptic solvers for transonic flow computations," Aeordynamics Analyses Requiring Advanced Computers, NASA SP347, 1975. (To appear.)
 [37]
 E. D. MARTIN, "A fast semidirect method for computing transonic aerodynamic flows," Proceedings of the AIAA 2nd Computational Fluid Dynamics Conference, June 1975. (To appear.) MR 0459290 (56:17484)
 [38]
 C. C. PAIGE & M. A. SAUNDERS, "Solutions of sparse indefinite systems of equations," SIAM J. Numer. Anal., v. 12, 1975, pp. 617629. MR 0383715 (52:4595)
 [39]
 V. PEREYRA, W. PROSKUROWSKI & O. WIDLUND, "On a family of elliptic difference schemes suggested by HeinzOtto Kreiss." (To appear.)
 [40]
 C. S. PESKIN, Personal communication.
 [41]
 I. G. PETROVSKIĬ, Lectures on Partial Differential Equations, GITTL, Moscow, 1950; English transl., Interscience, New York, 1954. MR 13, 241; 16, 478. MR 0043322 (13:241f)
 [42]
 A. SHIEH, Fast Poisson Solver on Nonrectangular Domains, Ph. D. Thesis, New York University, June 1976.
 [43]
 G. STRANG & G. J. FIX, An Analysis of the Finite Element Method, PrenticeHall, Englewood Cliffs, N. J., 1973. MR 0443377 (56:1747)
 [44]
 V. THOMÉE, "On the convergence of difference quotients in elliptic problems," Numerical Solution of Field Problems in Continuum Physics, SIAMAMS Proc., vol. 2, Amer. Math. Soc., Providence, R. I., 1970, pp. 186200. MR 41 #4834. MR 0260206 (41:4834)
 [45]
 J. TODD (Editor), Survey of Numerical Analysis, McGrawHill, New York, 1962. MR 24 #B1271. MR 0135221 (24:B1271)
 [46]
 O. 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.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65N05,
35J05
Retrieve articles in all journals
with MSC:
65N05,
35J05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197604211024
PII:
S 00255718(1976)04211024
Article copyright:
© Copyright 1976 American Mathematical Society
