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

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]**A. BANEGAS, "Fast Poisson solvers for problems with sparsity,"*Math. Comp.*, v. 32, 1978, pp. 441-446. MR**0483338 (58:3351)****[2]**R. E. BANK, "Marching algorithms for elliptic boundary value problems. II: The variable coefficient case,"*SIAM J. Numer. Anal.*, v. 14, 1977, pp. 950-970. MR**0502001 (58:19197b)****[3]**R. E. BANK & D. J. ROSE, "Marching algorithms for elliptic boundary value problems. I: The constant coefficient case,"*SIAM J. Numer. Anal.*, v. 14, 1977, pp. 792-829. MR**0502000 (58:19197a)****[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 & 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. 753-763. 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. 722-736. MR**0292316 (45:1403)****[8]**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**0287717 (44:4920)****[9]**L. COLLATZ,*The Numerical Treatment of Differential Equations*, Springer-Verlag, Berlin and New York, 1960. MR**784038 (86b:65003)****[10]**P. CONCUS, G. H. GOLUB & D. P. O'LEARY, "A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations,"*Sparse Matrix Computations*(J. R. Bunch and D. J. Rose, Eds.), Academic Press, New York, 1976, pp. 309-332. MR**0501821 (58:19069)****[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]**J. W. DANIEL, "The conjugate gradient method for linear and nonlinear operator equations,"*SIAM J. Numer. Anal.*, v. 4, 1967, pp. 10-26. MR**0217987 (36:1076)****[13]**S. C. EISENSTAT, "Complexity bounds for Gaussian elimination." (To appear.)**[14]**S. C. EISENSTAT, M. H. SCHULTZ & A. H. SHERMAN, "Applications of an element model for Gaussian elimination,"*Sparse Matrix Computations*(J. R. Bunch and D. J. Rose, Eds.), Academic Press, New York, 1976, pp. 85-96. MR**0458822 (56:17022)****[15]**M. ENGELI, TH. GINSBURG, H. RUTISHAUSER & E. STIEFEL,*Refined Iterative Methods for Computation of the Solution and the Eigenvalues of Self-Adjoint Boundary Value Problems*, Birkhäuser, Basel-Stuttgart, 1959. MR**0145689 (26:3218)****[16]**D. FISCHER, G. GOLUB, O. HALD, C. LEIVA & O. WIDLUND, "On Fourier-Toeplitz methods for separable elliptic problems,"*Math. Comp.*, v. 28, 1974, pp. 349-368. MR**0415995 (54:4072)****[17]**G. E. FORSYTHE & W. R. WASOW,*Finite Difference Methods for Partial Differential Equations*, Wiley, New York, 1960. MR**0130124 (23:B3156)****[18]**P. R. GARABEDIAN,*Partial Differential Equations*, Wiley, New York, 1964. MR**0162045 (28:5247)****[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]**A. GEORGE, "Nested dissection of a regular finite element mesh,"*SIAM J. Numer. Anal.*, v. 10, 1973, pp. 345-363. MR**0388756 (52:9590)****[21]**R. M. HAYES, "Iterative methods of solving linear problems on Hubert space,"*Contributions to the Solution of Systems of Linear Equations and the Determination of Eigenvalues*(O. Taussky, Ed.), Nat. Bur. Standards Appl. Math. Series, Vol. 39, 1954, pp. 71-103. MR**0066563 (16:597b)****[22]**M. R. HESTENES,*The Conjugate Gradient Method for Solving Linear Systems*, Proc. Sympos. Appl. Math., Vol. 6, Amer. Math. Soc., Providence, R. I., 1956, pp. 83-102. MR**0084178 (18:824c)****[23]**M. R. HESTENES & E. STIEFEL, "Methods of conjugate gradients for solving linear systems,"*J. Res. Nat. Bur. Standards*, v. 49, 1952, pp. 409-436. MR**0060307 (15:651a)****[24]**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**0213048 (35:3913)****[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]**A. J. HOFFMAN, M. S. MARTIN & D. J. ROSE, "Complexity bounds for regular finite difference and finite element grids,"*SIAM J. Numer. Anal.*, v. 10, 1973, pp. 364-369. MR**0347065 (49:11785)****[29]**A. S. HOUSEHOLDER,*The Theory of Matrices in Numerical Analysis*, Blaisdell, New York, 1964. MR**0175290 (30:5475)****[30]**H. Y. HUANG, "Unified approach to quadratically convergent algorithms for function minimization,"*J. Optimization Theory Appl.*, v. 5, 1970, pp. 405-423. MR**0288939 (44:6134)****[31]**S. KANIEL, "Estimates for some computational techniques in linear algebra,"*Math. Comp.*, v. 20, 1966, pp. 369-378. MR**0234618 (38:2934)****[32]**O. D. KELLOGG,*Foundations of Potential Theory*, Springer-Verlag, Berlin, Heidelberg, New York, 1967. MR**0222317 (36:5369)****[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. 255-282. MR**0042791 (13:163d)****[34]**D. G. LUENBERGER,*Introduction to Linear and Nonlinear Programming*, Addison-Wesley, Reading, Mass., 1973.**[35]**E. D. MARTIN, "A generalized capacity matrix technique for computing aerodynamic flows,"*Internat. J. Comput. Fluids*, v. 2, 1974, pp. 79-97. MR**0347233 (49:11953)****[36]**G. E. MYERS, "Properties of the conjugate gradient and Davidon methods,"*J. Optimization Theory Appl.*, v. 2, 1968, pp. 209-219. MR**0250451 (40:3688)****[37]**J.-C. NEDELEC & J. PLANCHARD, "Une méthode variationeile d'éléments finis pour la résolution numérique d'un problème extérieur dans ," R.A.I.R.O., v. 7-R, 1973, pp. 105-129. MR**0424022 (54:11992)****[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]**V. PEREYRA, W. PROSKUROWSKI & O. WIDLUND, "High order fast Laplace solvers for the Dirichlet problem on general regions,"*Math. Comp.*, v. 31, 1977, pp. 1-16. MR**0431736 (55:4731)****[40]**G. N. POLOZHII,*The Method of Summary Representation for Numerical Solution of Problems of Mathematical Physics*, Pergamon Press, New York, 1965. MR**0230481 (37:6043)****[41]**W. PROSKUROWSKI, "On the numerical solution of the eigenvalue problem of the Laplace operator by the capacitance matrix method,"*Computing*, v. 20, 1978, pp. 139-151. MR**619766 (82f:65106)****[42]**W. PROSKUROWSKI, "Numerical solution of Helmholtz's equation by implicit capacitance matrix methods,"*ACM Trans. Math. Software*, v. 5, 1979, pp. 36-49. MR**520747 (80b:65129)****[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]**W. PROSKUROWSKI & O. WIDLUND, "On the numerical solution of Helmholtz's equation by the capacitance matrix method,"*Math. Comp.*, v. 30, 1976, pp. 433-468. Appeared also as an ERDA-NYU report. MR**0421102 (54:9107)****[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.*, v. 29, 1978, pp. 307-327. MR**0659094 (58:31951)****[48]**A. S. L. SHIEH, "Fast Poisson solvers on general two dimensional regions for the Dirichlet problem,"*Numer. Math.*, v. 31, 1979, pp. 405-429. MR**516582 (80d:65110)****[49]**G. STRANG &. G. J. FIX,*An Analysis of the Finite Element Method*, Prentice-Hall, Englewood Cliffs, N. J., 1973. MR**0443377 (56:1747)****[50]**P. N. SWARZTRAUBER, "A direct method for the discrete solution of separable elliptic equations,"*SIAM J. Numer. Anal.*, v. 11, 1974, pp. 1136-1150. MR**0368399 (51:4640)****[51]**P. 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.*, v. 19, 1977, pp. 490-501. MR**0438732 (55:11639)****[52]**P. N. SWARZTRAUBER & R. A. SWEET, "The direct solution of the discrete Poisson equation on a disk,"*SIAM J. Numer. Anal.*, v. 10, 1973, pp. 900-907. MR**0368454 (51:4695)****[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]**R. SWEET, "A cyclic reduction algorithm for solving block tridiagonal systems of arbitrary dimension,"*SIAM J. Numer. Anal.*, v. 14, 1977, pp. 706-720. MR**0445859 (56:4192)****[55]**V. THOMEE, "On the convergence of difference quotients in elliptic problems,"*Numerical Solution of Field Problems in Continuum Physics*, SIAM-AMS Proc., Vol. 2, Amer. Math. Soc., Providence, R. I., 1970, pp. 186-200. MR**0260206 (41:4834)****[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]**O. WIDLUND,*Capacitance Matrix Methods for Helmholtz's Equation on General Bounded Regions*, Proc. Oberwolfach meeting 1976, Springer Lecture Notes in Math., Vol. 631, 1978, pp. 209-219. MR**0474873 (57:14504)****[58]**R. B. WILHELMSON & J. H. ERICKSEN, "The direct solutions for Poisson's equation in three dimensions,"*J. Computational Phys.*, v. 25, 1977, pp. 319-331. MR**0474874 (57:14505)**

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