Capacitance matrix methods for the Helmholtz equation on general three-dimensional regions

Authors:
Dianne P. O'Leary and Olof Widlund

Journal:
Math. Comp. **33** (1979), 849-879

MSC:
Primary 65N99; Secondary 65F10

DOI:
https://doi.org/10.1090/S0025-5718-1979-0528044-7

MathSciNet review:
528044

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Capacitance matrix methods provide techniques for extending the use of fast Poisson solvers to arbitrary bounded regions. These techniques are further studied and developed with a focus on the three-dimensional case. A discrete analogue of classical potential theory is used as a guide in the design of rapidly convergent iterative methods. Algorithmic and programming aspects of the methods are also explored in detail. Several conjugate gradient methods are discussed for the solution of the capacitance matrix equation. A fast Poisson solver is developed which is numerically very stable even for indefinite Helmholtz equations. Variants thereof allow substantial savings in primary storage for problems on very fine meshes. Numerical results show that accurate solutions can be obtained at a cost which is proportional to that of the fast Helmholtz solver in use.

**[1]**Alexandra Banegas,*Fast Poisson solvers for problems with sparsity*, Math. Comp.**32**(1978), no. 142, 441–446. MR**483338**, https://doi.org/10.1090/S0025-5718-1978-0483338-8**[2]**Randolph E. Bank and Donald J. Rose,*Marching algorithms for elliptic boundary value problems. I. The constant coefficient case*, SIAM J. Numer. Anal.**14**(1977), no. 5, 792–829. MR**502000**, https://doi.org/10.1137/0714055**[3]**Randolph E. Bank and Donald J. Rose,*Marching algorithms for elliptic boundary value problems. I. The constant coefficient case*, SIAM J. Numer. Anal.**14**(1977), no. 5, 792–829. MR**502000**, https://doi.org/10.1137/0714055**[4]**C. G. BROYDEN, "Quasi-Newton methods" in*Numerical Methods for Unconstrained Optimization*(W. Murray, Ed.), Academic Press, New York, 1972, pp. 87-106.**[5]**O. BUNEMAN,*A Compact Non-Iterative Poisson Solver*, Report SUIPR-294, Inst. Plasma Research, Standford 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**362944**, 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**292316**, 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**287717**, 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, Gene H. Golub, and Dianne P. O’Leary,*A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations*, Sparse matrix computations (Proc. Sympos., Argonne Nat. Lab., Lemont, Ill., 1975) Academic Press, New York, 1976, pp. 309–332. MR**0501821****[11]**J. W. COOLEY, P. A. W. LEWIS & P. D. WELSH, "The fast Fourier transform algorithm: Programming considerations in the calculation of sine, cosine and Laplace transforms,"*J. Sound Vib.*, v. 12, 1970, pp. 315-337.**[12]**James W. Daniel,*The conjugate gradient method for linear and nonlinear operator equations*, SIAM J. Numer. Anal.**4**(1967), 10–26. MR**217987**, https://doi.org/10.1137/0704002**[13]**S. C. EISENSTAT, "Complexity bounds for Gaussian elimination." (To appear.)**[14]**S. C. Eisenstat, M. H. Schultz, and A. H. Sherman,*Applications of an element model for Gaussian elimination*, Sparse matrix computations (Proc. Sympos., Argonne Nat. Lab., Lemont, Ill., 1975) Academic Press, New York, 1976, pp. 85–96. MR**0458822****[15]**M. Engeli, Th. Ginsburg, H. Rutishauser, and E. Stiefel,*Refined iterative methods for computation of the solution and the eigenvalues of self-adjoint boundary value problems*, Mitt. Inst. Angew. Math. Zürich. No.**8**(1959), 107. MR**0145689****[16]**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**415995**, https://doi.org/10.1090/S0025-5718-1974-0415995-2**[17]**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****[18]**P. R. Garabedian,*Partial differential equations*, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR**0162045****[19]**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.**[20]**Alan George,*Nested dissection of a regular finite element mesh*, SIAM J. Numer. Anal.**10**(1973), 345–363. MR**388756**, https://doi.org/10.1137/0710032**[21]**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****[22]**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****[23]**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****[24]**R. W. Hockney,*A fast direct solution of Poisson’s equation using Fourier analysis*, J. Assoc. Comput. Mach.**12**(1965), 95–113. MR**213048**, https://doi.org/10.1145/321250.321259**[25]**R. W. HOCKNEY, "Formation and stability of virtual electrodes in a cylinder,"*J. Appl. Phys.*, v. 39, 1968, pp. 4166-4170.**[26]**R. W. HOCKNEY, "The potential calculation and some applications,"*Methods in Computational Physics*, Vol. 9, Academic Press, New York, 1970.**[27]**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.**[28]**Alan J. Hoffman, Michael S. Martin, and Donald J. Rose,*Complexity bounds for regular finite difference and finite element grids*, SIAM J. Numer. Anal.**10**(1973), 364–369. MR**347065**, https://doi.org/10.1137/0710033**[29]**Alston S. Householder,*The theory of matrices in numerical analysis*, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1964. MR**0175290****[30]**H. Y. Huang,*Unified approach to quadratically convergent algorithms for function minimization*, J. Optim. Theory Appl.**5**(1970), 405–423. MR**288939**, https://doi.org/10.1007/BF00927440**[31]**Shmuel Kaniel,*Estimates for some computational techniques in linear algebra*, Math. Comp.**20**(1966), 369–378. MR**234618**, https://doi.org/10.1090/S0025-5718-1966-0234618-4**[32]**Oliver Dimon Kellogg,*Foundations of potential theory*, Reprint from the first edition of 1929. Die Grundlehren der Mathematischen Wissenschaften, Band 31, Springer-Verlag, Berlin-New York, 1967. MR**0222317****[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**347233**, https://doi.org/10.1016/0045-7930(74)90006-1**[36]**Geraldine E. Myers,*Properties of the conjugate-gradient and Davidon methods*, J. Optim. Theory Appl.**2**(1968), 209–219. MR**250451**, https://doi.org/10.1007/BF00937366**[37]**J.-C. Nédélec and J. Planchard,*Une méthode variationnelle d’éléments finis pour la résolution numérique d’un problème extérieur dans 𝑅³*, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge**7**(1973), no. no. , no. R-3, 105–129 (French, with English summary). MR**424022****[38]**C. C. PAIGE,*The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices*, Ph.D. thesis, London University, Institute of Computer Science, 1971.**[39]**Victor Pereyra, Wlodzimierz Proskurowski, and Olof Widlund,*High order fast Laplace solvers for the Dirichlet problem on general regions*, Math. Comp.**31**(1977), no. 137, 1–16. MR**431736**, https://doi.org/10.1090/S0025-5718-1977-0431736-X**[40]**G. N. Polozhii,*The method of summary representation for numerical solution of problems of mathematical physics*, Authorized translation incorporating revisions and new material supplied by the author. Translated from the Russian by G. J. Tee. Translation edited by K. L. Stewart. International Series of Monographs in Pure and Applied Mathematics, Vol. 79, Pergamon Press, Oxford-New York-Paris, 1965. MR**0230481****[41]**W. Proskurowski,*On the numerical solution of the eigenvalue problem of the Laplace operator by a capacitance matrix method*, Computing**20**(1978), no. 2, 139–151 (English, with German summary). MR**619766**, https://doi.org/10.1007/BF02252343**[42]**Włodzimierz Proskurowski,*Numerical solution of Helmholtz’s equation by implicit capacitance matrix methods*, ACM Trans. Math. Software**5**(1979), no. 1, 36–49. MR**520747**, https://doi.org/10.1145/355815.355818**[43]**W. PROSKUROWSKI,*Four FORTRAN Programs for Numerically Solving Helmholtz's Equation in an Arbitrary Bounded Planar Region*, Report LBL-7516, Lawrence Berkeley Laboratory, 1978.**[44]**Wlodzimierz Proskurowski and Olof Widlund,*On the numerical solution of Helmholtz’s equation by the capacitance matrix method*, Math. Comp.**30**(1976), no. 135, 433–468. MR**421102**, https://doi.org/10.1090/S0025-5718-1976-0421102-4**[45]**W. PROSKUROWSKI & O. WIDLUND, "A finite element-capacitance method for the Neumann problem for Laplace's equation." (To appear.)**[46]**A. S. L. SHIEH,*Fast Poisson Solver on Nonrectangular Domains*, Ph.D. thesis, New York University, 1976.**[47]**A. S. L. Shieh,*On the convergence of the conjugate gradient method for singular capacitance matrix equations from the Neumann problem of the Poisson equation*, Numer. Math.**29**(1977/78), no. 3, 307–327. MR**659094**, https://doi.org/10.1007/BF01389215**[48]**A. S. L. Shieh,*Fast Poisson solvers on general two-dimensional regions for the Dirichlet problem*, Numer. Math.**31**(1978/79), no. 4, 405–429. MR**516582**, https://doi.org/10.1007/BF01404568**[49]**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****[50]**Paul N. Swarztrauber,*A direct method for the discrete solution of separable elliptic equations*, SIAM J. Numer. Anal.**11**(1974), 1136–1150. MR**368399**, https://doi.org/10.1137/0711086**[51]**Paul N. Swarztrauber,*The methods of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of Poisson’s equation on a rectangle*, SIAM Rev.**19**(1977), no. 3, 490–501. MR**438732**, https://doi.org/10.1137/1019071**[52]**Paul N. Swarztrauber and Roland A. Sweet,*The direct solution of the discrete Poisson equation on a disk*, SIAM J. Numer. Anal.**10**(1973), 900–907. MR**368454**, https://doi.org/10.1137/0710075**[53]**P. SWARZTRAUBER & R. SWEET,*Efficient FORTRAN Subprograms for the Solution of Elliptic Partial Differential Equations*, Report NCAR-TN/IA-109, National Center for Atmospheric Research, Boulder, Colorado, 1975.**[54]**Roland A. Sweet,*A cyclic reduction algorithm for solving block tridiagonal systems of arbitrary dimension*, SIAM J. Numer. Anal.**14**(1977), no. 4, 706–720. MR**445859**, https://doi.org/10.1137/0714048**[55]**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****[56]**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*(D. J. Rose and R. A. Willoughby, Ed.), Plenum Press, New York, 1972, pp. 121-134.**[57]**Olof Widlund,*Capacitance matrix methods for Helmholtz’s equation on general bounded regions*, Numerical treatment of differential equations (Proc. Conf., Math. Forschungsinst., Oberwolfach, 1976) Springer, Berlin, 1978, pp. 209–219. Lecture Notes in Math., Vol. 631. MR**0474873****[58]**Robert B. Wilhelmson and James H. Ericksen,*Direct solutions for Poisson’s equation in three dimensions*, J. Comput. Phys.**25**(1977), no. 4, 319–331. MR**474874**, https://doi.org/10.1016/0021-9991(77)90001-8

Retrieve articles in *Mathematics of Computation*
with MSC:
65N99,
65F10

Retrieve articles in all journals with MSC: 65N99, 65F10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1979-0528044-7

Article copyright:
© Copyright 1979
American Mathematical Society