Algorithm 720: An algorithm for adaptive cubature over a collection of 3-dimensional simplices

ABSTRACT

An adaptive algorithm for computing an approximation to the integral of each element in a vector of functions over a 3-dimensional region covered by simplices is presented. The algorithm is encoded in FORTRAN 77. Locally, a cubature formula of degree 8 with 43 points is used to approximate an integral. The local error estimate is based on the same evaluation points. The error estimation procedure tries to decide whether the approximation for each function has asymptotic behavior, and different actions are taken depending on that decision. The simplex with the largest error is subdivided into 8 simplices. The local procedure is then applied to each new region. This procedure is repeated until convergence.

REFERENCES

• 1: NAG FORTRAN LIBRARY MANUAL, MARK 10, 1983. The Numerical Algorithm Group, Oxford, U.K.
• 2: BECKERS, M., AND HAEGEMANS, A. The construction of cubature formulae for the tetrahedron. Rep. TW 128, Katholleke Umv. Leuven, Belgium, 1990.
• 3: BERNTSEN, J. Cautious adaptive numerical integration over the 3-cube. Reports in Informatics 17, Dept. of Informatics, Univ. of Bergen, 1985.
• 4: BERNTSEN, J., COOLS, R., AND ESPELID, T O. A test of DCUTET. Reports in Informatics 46, Dept. of Informatms, Univ. of Bergen, 1990.
• 5: Jarle Berntsen , Terje O. Espelid, Algorithm 706; DCUTRI: an algorithm for adaptive cubature over a collection of triangles, ACM Transactions on Mathematical Software (TOMS), v.18 n.3, p.329-342, Sept. 1992 [doi>10.1145/131766.131772]
• 6: Jarle Berntsen , Terje O. Espelid, Error estimation in automatic quadrature routines, ACM Transactions on Mathematical Software (TOMS), v.17 n.2, p.233-252, June 1991 [doi>10.1145/108556.108575]
• 7: Jarle Berntsen , Terje O. Espelid , Alan Genz, An adaptive algorithm for the approximate calculation of multiple integrals, ACM Transactions on Mathematical Software (TOMS), v.17 n.4, p.437-451, Dec. 1991 [doi>10.1145/210232.210233]
• 8: Jarle Berntsen , Terje O. Espelid , Alan Genz, Algorithm 698; DCUHRE: an adaptive multidemensional integration routine for a vector of integrals, ACM Transactions on Mathematical Software (TOMS), v.17 n.4, p.452-456, Dec. 1991 [doi>10.1145/210232.210234]
• 9: COWELL, W. R., AND GARBOW, S B Users Guide to Toolpack /1 (Release 2) in a Umx Enmronment Tech. Rep. ANL~87-12, Argonne National Laboratories, 1987.
• 10: DE DONCKER, E New Euler-Maclaurin expansions and their application to quadrature over the s-dimensional Simplex. Math Comput. 33 (1979), 1003-1018,
• 11: ESPELID, T.O. Integratmn rules, null rules and error estimation. Reports in Informatics 33, Dept. of Informatics, Univ. of Bergen, 1988.
• 12: GENZ, A. C., AND MALIK, A. A. An adaptive algorithm for numerical integration over an N-dimensional rectangular region J. Comput. Appl. Math. 6 (1980), 295 302.
• 13: GRUNDM~N, A., A~D MOLLER, H.M. Invariant integration formulas for the n-simplex by combinatorial methods. SIAM J. Numer. Anal. 15 (1978), 282 290.
• 14: L~ESS, J.N. Symmetric mtegratmn rules for hypercubes III. Construction of integration rules using null rules. Math. Comput. 19 (1965), 625 637.
• 15: J. N. Lyness , J. J. Kaganove, Comments on the Nature of Automatic Quadrature Routines, ACM Transactions on Mathematical Software (TOMS), v.2 n.1, p.65-81, March 1976 [doi>10.1145/355666.355671]
• 16: LYNESS, J. N., AND tC~GANOVE, J. J. A technique for comparing automatic quadrature routines. Comput. J. 20 (1977), 170-177
• 17: VAN DOOREN, P., AND DE RIDDER, L. An adaptive algorithm for numerical integration over an N-dimensional cube. J. Comput. Appl. Math. 2 (1976), 207-217.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Multidimensional (multiple) quadrature; Adaptive and iterative quadrature
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Reliability and robustness

General Terms:
Algorithms, Reliability

Keywords:
automatic integration, cubature, cubature rules, error estimation, null rules, symmetry, tetrahedrons