Algorithm 732: solvers for self-adjoint elliptic problems in irregular two-dimensional domains

ABSTRACT

Software is provided for the rapid solution of certain types of elliptic equations in rectangular and irregular domains. Specifically, solutions are found in two dimensions for the nonseparable self-adjoint elliptic problem ▽˙g▽y =f , where g and f are given functions of x and y, in two-dimensional polygonal domains with Dirichlet boundary conditions. Helmholtz and Poisson problems in polygonal domains and the general variable coefficient problem i.e.,g≠1 in a rectangular domain may be treated as special cases. The method of solution combines the use of the capacitance matrix method, to treat the irregular boundary, with an efficient iterative method (using the Laplacian as preconditioner) to deal 2 with nonseparability. Each iterative step thus involves solving the Poisson equation in a rectangular domain. The package includes separate, easy-to-use routines for the Helmholtz problem and the general problem in rectangular and general polygonal domains, and example driver routines for each. Both single- and double-precision routines are provided.Second-order-accurate finite differencing is employed. Storage requirements increase approximately as p2 + n2, where p is the number of irregular boundary points and where n is the linear domain dimension. The preprocessing time (the capacitance matrix calculation) varies as pn2 log n, and the solution time varies as n2 log n. If the equations are to be solved repeatedly in the same geometry, but with different source or diffusion functions, the capacitance matrix need only be calculated once, and hence the algorithm is particularly efficient for such cases.

REFERENCES

• 1: CONCUS, P., ANn GOLUB, G. H. 1973. Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations. SIAM J. Numer. Anal. 10, 1103-1120.
• 2: CUMMINS, P. F., AND MYSAK, L.A. 1988. A quasi-geostrophic circulation model of the Northeast Pacific. Part I: A preliminary numerical experiment. J. Phys. Ocean. 18, 1261-1286.
• 3: DONGAR~, J. J., MOLER, C. B., BUNCH, J. R., AND STEWART, G.W. 1979. LINPACK User's Guide. SIAM Publications, Philadelphia, Pa.
• 4: HOCI~EY, R.W. 1970. The potential calculation and some applications. In Methods of Computational Physics, vol. 9, B. Adler, S. Fernbach, and M. Rotenberg, Eds. Academic Press, New York, 135-211.
• 5: A. Pares-Sierra , G. K. Vallis, A fast semi-direct method for the numerical solution of non-separable elliptic equations in irregular domains, Journal of Computational Physics, v.82 n.2, p.398-412, June 1989 [doi>10.1016/0021-9991(89)90055-7]
• 6: Wlodzimierz Proskurowski, Algorithm 593: A Package for the Helmholtz Equation in Nonrectangular Planar Regions, ACM Transactions on Mathematical Software (TOMS), v.9 n.1, p.117-124, March 1983 [doi>10.1145/356022.356028]
• 7: PROSKUROWSKI, W., AND WmLUND, O. 1976. On the numerical solution of Helmholtz's equation by the capacitance matrix method. Math. Comput. 30,433-468.
• 8: John R. Rice , Ronald F. Boisvert, Solving elliptic problems using ELLPACK, Springer-Verlag New York, Inc., New York, NY, 1985
• 9: SWA~ZT~UBER, P.N. 1977. The methods of cyclic reduction, Fourier analysis and the FACR algorithm for the discrete solution of the Poisson equation on a rectangle. SIAM Rev. 19, 490-501.
• 10: Paul N. Swarztrauber , Roland A. Sweet, Algorithm 541: Efficient Fortran Subprograms for the Solution of Separable Elliptic Partial Differential Equations [D3], ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.352-364, Sept. 1979 [doi>10.1145/355841.355850]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.8 Partial Differential Equations
          Subjects: Elliptic equations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

General Terms:
Algorithms

Keywords:
Green's function, capacitance iteration, capacitance matrix, elliptic equations, fast Poisson solvers