Algorithm 706: DCUTRI: an algorithm for adaptive cubature over a collection of triangles

ABSTRACT

An adaptive algorithm for computing an approximation to the integral of each element in a vector function f(x,y) over a two-dimensional region made up of triangles is presented. A FORTRAN implementation of the algorithm is included. The basic cubature rule used over each triangle is a 37-point symmetric rule of degree 13. Based on the same evaluation points the local error for each element in the approximation vector and for each triangle is computed using a sequence of null rule evaluations. A sophisticated error-estimation procedure tries, in a cautious manner, to decide whether we have asymptotic behavior locally for each function. Different actions are taken depending on that decision, and the procedure takes advantage of the basic rule's polynomial degree when computing the error estimate in the asymptotic case.

REFERENCES

• 1: BERNTSEN, J. Cautious adaptive numerical integration over the 3-cube. Reports in Informatics 17, Dept. of inf., Univ. of Bergen, 1985.
• 2: BERNTSEN, J. TR1TST: A subroutine for evaluating the performance of subroutines for automatic integratmn over triangles. Reports in Informatics 34, Dept of Inf, Univ of Bergen, 1989.
• 3: BERNTSEN, J., AND ESPELID, T.O. A Test of DCUTRI and TWODQD. Reports in Informatics 40, Dept. of Inf., Univ. of Bergen, 1989.
• 4: BERNTSEN, J., AND ESPEL1D, T.O. Degree 13 symmetric quadrature rules for the triangle. Reports in Informatics 44, Dept. of Inf., Univ. of Bergen, 1990.
• 5: 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]
• 6: 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]
• 7: 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]
• 8: COWELL, W. R., AND GARBOW, S B. Users Guide to TooIpack/1 (Release 2) m a Unix Environment. Tech. Rep. ANL-87-12, Argonne National Labs., 1987.
• 9: Elise de Doncker , Ian Robinson, Algorithm 612: TRIEX: Integration Over a TRIangle Using Nonlinear EXtrapolation, ACM Transactions on Mathematical Software (TOMS), v.10 n.1, p.17-22, March 1984 [doi>10.1145/356068.356070]
• 10: ESPELID. T.O. Integration rules, null rules and error estimation. Reports in Informatics 33, Dept. of Informatics, Univ. of Bergen, 1988.
• 11: HAEGEMANS, A. An algorithm for the automatic integration over a triangle. Cornp~t~lzg 19 (1977), 179 187.
• 12: 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]
• 13: 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]
• 14: LYNESS, J.N. Symmetric integration rules for hypercubes III. Construction of integration rules using null rules. Math. Comput. 19 (1965), 625-637.
• 15: LYNESS, J. N., AND JESPERSEN, D. Moderate degree symmetric quadrature rules for the triangle, d. Inst. Math. Appl. 15 (1975), 19-32.
• 16: 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]
• 17: LSXNESS, J. N., AND KAGANOVE, J. J. A technique for comparing automatic quadrature routines. Cornput. d. 20 (1977), 170-177.
• 18: PIESSENS, R., DE DONCKER-KAPENGA E., UBERHUBER, C W., AND KAHANER, D. K. QUAD- PACK, A subroutine package for automatic integration. Series in Computational Math., 1, Springer-Verlag, New York, 1983.
• 19: John R. Rice, A Metalgorithm for Adaptive Quadrature, Journal of the ACM (JACM), v.22 n.1, p.61-82, Jan. 1975 [doi>10.1145/321864.321870]

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, Reliability

Keywords:
automatic integration, cubature, cubature rules, error estimation, null rules, symmetry, triangular regions