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

O’Leary, Dianne P.; Widlund, Olof

doi:10.1090/S0025-5718-1979-0528044-7

Capacitance matrix methods for the Helmholtz equation on general three-dimensional regions
HTML articles powered by AMS MathViewer

by Dianne P. O’Leary and Olof Widlund PDF

Math. Comp. 33 (1979), 849-879 Request permission

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.

References

Alexandra Banegas, Fast Poisson solvers for problems with sparsity, Math. Comp. 32 (1978), no. 142, 441–446. MR 483338, DOI 10.1090/S0025-5718-1978-0483338-8
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, DOI 10.1137/0714055
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, DOI 10.1137/0714055

Numerical Methods for Unconstrained Optimization

A Compact Non-Iterative Poisson Solver

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, DOI 10.1137/0711061
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, DOI 10.1137/0708066
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, DOI 10.1137/0707049
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, DOI 10.1007/978-3-0348-5454-2
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

J. Sound Vib.

James W. Daniel, The conjugate gradient method for linear and nonlinear operator equations, SIAM J. Numer. Anal. 4 (1967), 10–26. MR 217987, DOI 10.1137/0704002
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
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 8 (1959), 107. MR 145689
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, DOI 10.1090/S0025-5718-1974-0415995-2
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
P. R. Garabedian, Partial differential equations, John Wiley & Sons, Inc., New York-London-Sydney, 1964. MR 0162045

The Use of Direct Methods for the Solution of the Discrete Poisson Equation on Non-Rectangular Regions

Alan George, Nested dissection of a regular finite element mesh, SIAM J. Numer. Anal. 10 (1973), 345–363. MR 388756, DOI 10.1137/0710032
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
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
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, DOI 10.6028/jres.049.044
R. W. Hockney, A fast direct solution of Poisson’s equation using Fourier analysis, J. Assoc. Comput. Mach. 12 (1965), 95–113. MR 213048, DOI 10.1145/321250.321259

J. Appl. Phys.

Methods in Computational Physics

A Fast Direct Poisson Solver for the Rectangle Allowing Some Mixed Boundary Conditions and Internal Electrodes

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, DOI 10.1137/0710033
Alston S. Householder, The theory of matrices in numerical analysis, Blaisdell Publishing Co. [Ginn and Co.], New York-Toronto-London, 1964. MR 0175290
H. Y. Huang, Unified approach to quadratically convergent algorithms for function minimization, J. Optim. Theory Appl. 5 (1970), 405–423. MR 288939, DOI 10.1007/BF00927440
Shmuel Kaniel, Estimates for some computational techniques in linear algebra, Math. Comp. 20 (1966), 369–378. MR 234618, DOI 10.1090/S0025-5718-1966-0234618-4
Oliver Dimon Kellogg, Foundations of potential theory, Die Grundlehren der mathematischen Wissenschaften, Band 31, Springer-Verlag, Berlin-New York, 1967. Reprint from the first edition of 1929. MR 0222317, DOI 10.1007/978-3-642-86748-4
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, DOI 10.6028/jres.045.026

Introduction to Linear and Nonlinear Programming

E. Dale Martin, A generalized-capacity-matrix technique for computing aerodynamic flows, Internat. J. Comput. & Fluids 2 (1974), no. 1, 79–97. MR 347233, DOI 10.1016/0045-7930(74)90006-1
Geraldine E. Myers, Properties of the conjugate-gradient and Davidon methods, J. Optim. Theory Appl. 2 (1968), 209–219. MR 250451, DOI 10.1007/BF00937366
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 $R^{3}$, Rev. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge 7 (1973), no. R-3, 105–129 (French, with English summary). MR 424022

The Computation of Eigenvalues and Eigenvectors of Very Large Sparse Matrices

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, DOI 10.1090/S0025-5718-1977-0431736-X
G. N. Polozhii, The method of summary representation for numerical solution of problems of mathematical physics, International Series of Monographs in Pure and Applied Mathematics, Vol. 79, Pergamon Press, Oxford-New York-Paris, 1965. 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. MR 0230481
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, DOI 10.1007/BF02252343
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, DOI 10.1145/355815.355818

Four FORTRAN Programs for Numerically Solving Helmholtz’s Equation in an Arbitrary Bounded Planar Region

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, DOI 10.1090/S0025-5718-1976-0421102-4

Fast Poisson Solver on Nonrectangular Domains

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, DOI 10.1007/BF01389215
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, DOI 10.1007/BF01404568
Gilbert Strang and George J. Fix, An analysis of the finite element method, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973. MR 0443377
Paul N. Swarztrauber, A direct method for the discrete solution of separable elliptic equations, SIAM J. Numer. Anal. 11 (1974), 1136–1150. MR 368399, DOI 10.1137/0711086
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, DOI 10.1137/1019071
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, DOI 10.1137/0710075

Efficient FORTRAN Subprograms for the Solution of Elliptic Partial Differential Equations

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, DOI 10.1137/0714048
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

Sparse Matrices and Their Applications

Olof Widlund, Capacitance matrix methods for Helmholtz’s equation on general bounded regions, Numerical treatment of differential equations (Proc. Conf., Math. Forschungsinst., Oberwolfach, 1976) Lecture Notes in Math., Vol. 631, Springer, Berlin, 1978, pp. 209–219. MR 0474873
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, DOI 10.1016/0021-9991(77)90001-8