On the numerical solution of Helmholtz's equation by the capacitance matrix method

Authors:
Wlodzimierz Proskurowski and Olof Widlund

Journal:
Math. Comp. **30** (1976), 433-468

MSC:
Primary 65N05; Secondary 35J05

DOI:
https://doi.org/10.1090/S0025-5718-1976-0421102-4

MathSciNet review:
0421102

Full-text 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 well-conditioned 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-London, 1972. Mathematics in Science and Engineering, Vol. 88. MR**0359368****[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****[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****[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****[5]**O. BUNEMAN,*A Compact Non-Iterative Poisson Solver*, Report SUIPR-294, 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**, https://doi.org/10.1137/0711061**[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**, https://doi.org/10.1137/0708066**[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**, https://doi.org/10.1137/0707049**[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****[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**, https://doi.org/10.1137/0710092**[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. 315-337.**[12]**R. Courant and D. Hilbert,*Methods of mathematical physics. Vol. I*, Interscience Publishers, Inc., New York, N.Y., 1953. MR**0065391****[13]**James W. Daniel,*The conjugate gradient method for linear and nonlinear operator equations*, SIAM J. Numer. Anal.**4**(1967), 10–26. MR**0217987**, https://doi.org/10.1137/0704002**[14]**Fred W. Dorr,*The direct solution of the discrete Poisson equation on a rectangle.*, SIAM Rev.**12**(1970), 248–263. MR**0266447**, https://doi.org/10.1137/1012045**[15]**D. Fischer, G. Golub, O. Hald, C. Leiva, and O. Widlund,*On Fourier-Toeplitz methods for separable elliptic problems*, Math. Comp.**28**(1974), 349–368. MR**0415995**, https://doi.org/10.1090/S0025-5718-1974-0415995-2**[16]**George E. Forsythe and Wolfgang R. Wasow,*Finite-difference methods for partial differential equations*, Applied Mathematics Series, John Wiley & Sons, Inc., New York-London, 1960. MR**0130124****[17]**P. R. Garabedian,*Partial differential equations*, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR**0162045****[18]**J. A. GEORGE,*The Use of Direct Methods for the Solution of the Discrete Poisson Equation on Non-Rectangular 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****[21]**Magnus R. Hestenes,*The conjugate-gradient method for solving linear systems*, Proceedings of Symposia in Applied Mathematics. Vol. VI. Numerical analysis, McGraw-Hill Book Company, Inc., New York, for the American Mathematical Society, Providence, R. I., 1956, pp. 83–102. MR**0084178****[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****[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**, https://doi.org/10.1145/321250.321259**[24]**R. W. HOCKNEY, "Formation and stability of virtual electrodes in a cylinder,"*J. Appl. Phys.*, v. 39, 1968, pp. 4166-4170.**[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 4-*A 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 Poisson-Solvers*, 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 York-Toronto-London, 1964. MR**0175290****[29]**A. JAMESON,*Accelerated Iteration Schemes for Transonic Flow Calculations Using Fast Poisson Solvers*, N. Y. U. ERDA report C00-3077-82, 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**, https://doi.org/10.1137/0709016**[31]**Shmuel Kaniel,*Estimates for some computational techniques in linear algebra*, Math. Comp.**20**(1966), 369–378. MR**0234618**, https://doi.org/10.1090/S0025-5718-1966-0234618-4**[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; P. Noordhoff Ltd., Groningen, 1958. MR**0106537****[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****[34]**D. G. LUENBERGER,*Introduction to Linear and Nonlinear Programming*, Addison-Wesley, Reading, Mass., 1973.**[35]**E. Dale Martin,*A generalized-capacity-matrix technique for computing aerodynamic flows*, Internat. J. Comput. & Fluids**2**(1974), no. 1, 79–97. MR**0347233**, https://doi.org/10.1016/0045-7930(74)90006-1**[36]**E. D. MARTIN, "Progress in application of direct elliptic solvers for transonic flow computations,"*Aeordynamics Analyses Requiring Advanced Computers*, NASA SP-347, 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**, https://doi.org/10.2514/3.61432**[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**, https://doi.org/10.1137/0712047**[39]**V. PEREYRA, W. PROSKUROWSKI & O. WIDLUND, "On a family of elliptic difference schemes suggested by Heinz-Otto Kreiss." (To appear.)**[40]**C. S. PESKIN, Personal communication.**[41]**I. G. Petrovskiĭ,*Lekcii ob uravneniyah c častnymi proizvodnymi*, Gosudarstv. Izdat. Tehn.-Teor. Lit., Moscow-Leningrad,], 1950 (Russian). MR**0043322****[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*, Prentice-Hall, Inc., Englewood Cliffs, N. J., 1973. Prentice-Hall Series in Automatic Computation. MR**0443377****[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) Amer. Math. Soc., Providence, R. I., 1970, pp. 186–200. MR**0260206****[45]***Survey of numerical analysis*, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1962. MR**0135221****[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.

Retrieve articles in *Mathematics of Computation*
with MSC:
65N05,
35J05

Retrieve articles in all journals with MSC: 65N05, 35J05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1976-0421102-4

Article copyright:
© Copyright 1976
American Mathematical Society