An adaptive numerical cubature algorithm for simplices

ABSTRACT

A globally adaptive algorithm for numerical cubature of a vector of functions over a collection of n-dimensional simplices is described. The algorithm is based on a subdivision strategy that chooses for subdivision at each stage the subregion (of the input simplices) with the largest estimated error. This subregion is divided into two, three or four equal volume subregions by cutting selected edges. These edges are selected using information about the smoothness of the integrands in the edge directions. The algorithm allows a choice from several embedded cubature rule sequences for approximate integration and error estimation. A Fortran 95 implementation as a part of CUBPACK is also discussed. Testing of the algorithm is described.

REFERENCES

• 1: Jarle Berntsen , Ronald Cools , Terje O. Espelid, Algorithm 720; an algorithm for adaptive cubature over a collection of 3-dimensional simplices, ACM Transactions on Mathematical Software (TOMS), v.19 n.3, p.320-332, Sept. 1993 [doi>10.1145/155743.155785]
• 2: 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]
• 3: 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]
• 4: 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]
• 5: Ronald Cools, Monomial cubature rules since “Stroud”: a compilation—part 2, Journal of Computational and Applied Mathematics, v.112 n.1-2, p.21-27, Nov. 30, 1999 [doi>10.1016/S0377-0427(99)00229-0]
• 6: Cools, R. and Haegemans, A. 1992. CUBPACK: Progress report. In Numerical Integration---Recent Developments, Software and Applications, T. Espelid and A. Genz, Eds. NATO ASI Series C: Math. and Phys. Sciences, vol. 357. Kluwer Academic Publishers, Dordrecht, 305--315.
• 7: Ronald Cools , Ann Haegemans, Algorithm 824: CUBPACK: a package for automatic cubature; framework description, ACM Transactions on Mathematical Software (TOMS), v.29 n.3, p.287-296, September 2003 [doi>10.1145/838250.838253]
• 8: Ronald Cools , Philip Rabinowitz, Monomial cubature rules since “Stroud”: a compilation, Journal of Computational and Applied Mathematics, v.48 n.3, p.309-326, Nov. 30, 1993 [doi>10.1016/0377-0427(93)90027-9]
• 9: D01PAF: An automatic integration subroutine for integration over an N-simplex, Numerical Algorithms Group Limited, Wilkinson House, Jordan Hill Road, Oxford, United Kingdom OX2 8DR.
• 10: Ian Robinson, An Algorithm for Automatic Integration Over a Triangle Using Nonlinear Extrapolation, ACM Transactions on Mathematical Software (TOMS), v.10 n.1, p.1-16, March 1984 [doi>10.1145/356068.356069]
• 11: Engels, H. 1980. Numerical Quadrature and Cubature. Academic Press, London, England.
• 12: Espelid, T. and Genz, A. 1992. On the subdivision strategy in adaptive cubature algorithms for triangular regions. Reports in Informatics No 74, University of Bergen, Norway. December.
• 13: Fang, K.-T. and Wang, Y. 1994. Number Theoretic Methods in Statistics. Chapman and Hall, London, England.
• 14: Genz, A. 1987. A package for testing multiple integration subroutines. In Numerical Integration---Recent Developments, Software and Applications, P. Keast and G. Fairweather, Eds. NATO ASI Series C: Math. and Phys. Sciences, vol. 203. D. Reidel Publishing Company, Dordrecht, 337--340.
• 15: Alan Genz, An Adaptive Numerical Integration Algorithm for Simplices, Proceedings of the The First Great Lakes Computer Science Conference on Computing in the 90's, p.279-285, October 18-20, 1989
• 16: Grundmann, A. and Möller, H. 1978. Invariant integration formulas for the n-simplex by combinatorial methods. SIAM J. Numer. Anal. 15, 282--290.
• 17: Haegemans, A. 1977. Algorithm 34: An algorithm for the automatic integration over a triangle. Computing 19, 179--187.
• 18: David K. Kahaner , Ottis W. Rechard, TWODQD an adaptive routine for two-dimensional integration, Journal of Computational and Applied Mathematics, v.17 n.1-2, p.215-234, Feb. 1987 [doi>10.1016/0377-0427(87)90048-3]
• 19: David K. Kahaner , Mark B. Wells, An Experimental Algorithm for N-Dimensional Adaptive Quadrature, ACM Transactions on Mathematical Software (TOMS), v.5 n.1, p.86-96, March 1979 [doi>10.1145/355815.355821]
• 20: Patrick Keast, Cubature formulas for the surface of the sphere, Journal of Computational and Applied Mathematics, v.17 n.1-2, p.151-172, Feb. 1987 [doi>10.1016/0377-0427(87)90044-6]
• 21: D. P. Laurie, Algorithm 584: CUBTRI: Automatic Cubature over a Triangle, ACM Transactions on Mathematical Software (TOMS), v.8 n.2, p.210-218, June 1982 [doi>10.1145/355993.356001]
• 22: Lyness, J. and Cools, R. 1994. A survey of numerical cubature over triangles. In Mathematics of Computation 1943--1993: A Half-Century of Computational Mathematics, W. Gautschi, Ed. Proceedings of Symposia in Applied Mathematics, vol. 48. American Mathematical Society, Providence, R.I., 127--150.
• 23: Lyness, J. and Genz, A. 1980. On simplex trapezoidal rule families. SIAM J. Numer. Anal. 17, 126--147.
• 24: Mysovskikh, I. 1978. On a cubature formula for the simplex. Vopros. Vycisl. i Prikl. Mat., Tashkent 51, 74--90. (Russian).
• 25: Silvester, P. 1970. Symmetric quadrature formulae for simplexes. Math. Comput. 24, 95--100.
• 26: Stroud, A. 1969. A fifth degree integration formula for the n-simplex. SIAM J. Numer. Anal. 6, 90--98.
• 27: Stroud, A. 1971. Approximate Calculation of Multiple Integrals. Prentice-Hall, Englewood Cliffs, N.J.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Adaptive and iterative quadrature

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

General Terms:
Algorithms

Keywords:
Software, adaptive integration, cubature, multidimensional integration, simplex