Quadrature over tetrahedra

On 7/15/98 I posted the following the following message to NA Digest:

Colleagues here at Cornell who work on finite-element methods for structural analysis asked me about high-order quadrature rules for tetrahedra. The "classical" quadrature rule (e.g., A. Stroud and D. Secrest, "Gaussian Quadrature Formulas", Prentice Hall, 1966) for the tetrahedron is simply a product rule. For example, to extend the k-point Gaussian quadrature formula to the tetrahedron, one uses k^3 quadrature points arranged in a distorted cube inside the tetrahedron with appropriate polynomial weights. But this solution seems inefficient because many quadrature points are clustered (apparently needlessly) near one of the four vertices of the tetrahedron. So I'm wondering whether more efficient rules have been developed for this problem.

I have received helpful responses to this posting from many people, including Francois Bertrand, Ronald Cools, Martyn Field, Joseph Flaherty, Karin Gatermann, Alan Genz, P. Jimack, Kurt Lust, James Lyness, William Mitchell, Toshiro Ohsumi, Angelo Passaro, Margarit Rizea, Ulrich Ruede, Manil Suri, Howard Swann, Wim Sweldens, Mark Taylor, Mike Todd, and Yuan Xu.

I will attempt to summarize the status of this problem. For the unit cube, product Gaussian quadrature has the following desirable properties:

it's "optimal" in a certain sense,
it's symmetric, i.e., the rule is invariant under affine maps of the cube to itself,
the weights are all positive, and
the quadrature points are all interior to the unit cube.

As far as I can tell from the literature, there is no infinite family of quadrature rules known for the tetrahedron with all these properties. The product Gaussian rule lacks symmetry, although, as J. Lyness pointed out, it is otherwise a quite reasonable choice. But, for specific orders, symmetric rules are known with these properties. A classic work in this regard is:

A. Stroud, Approximate calculation of multiple integrals, Prentice Hall, 1971.

Since 1971, a number of new symmetric rules for the tetrahedron have been discovered that improve over this original work. These new rules are tabulated and reviewed by

R. Cools and P. Rabinowitz, Monomial Cubature Rules Since "Stroud", J. Comp. Appl. Math. 48 (1993), pp. 309-323.

A more recent survey is:

R. Cools, Constructing cubature formulae: the art behind the science, in A. Iserles, ed., Acta Numerica 1997, pp 1-54.

R. Cools has a web page that tracks the literature on quadrature: http://www.cs.kuleuven.ac.be/~ronald/Publi/survey.html. He also maintains a website with quadrature formulas (including points and weights) for tetrahedra and other domains on-line at http://www.cs.kuleuven.ac.be/~nines/research/ecf/ecf.html.

Some specific rules singled out by respondents include:

Y. Jinyun, Symmetric Gaussian formulae for tetrahedral regions, Comp. Meth. Appl. Mech. Engin., 43 (1984) 349-353
M. Gellert and R. Harbord, Moderate degree cubature formulas for 3D tetrahedral finite-element approximation, Comm. Appl. Num. Meth. 7 (1991) 487-495.

Several people mentioned work by D. Dunavant (Internat. J. Num. Meth. Engr 21 (1985) 1129-1148) for triangles, but I couldn't find the extension of this to tetrahedra, though H. Swann pointed out that the weighted product of a triangle rule with an interval rule yields a tetrahedral rule (asymmetric, but with more symmetry than product Gaussian quadrature).

In the case of quadrature for the purpose of computing stiffness matrix entries for finite element analysis (which was the motivation for my question) some more specialized techniques are available. Papers mentioned by respondents include

J. Lyness and U. Ruede, Cubature of integrands containing derivatives, Numerische Mathematik, 78 (1998) 439-461.
S. Sherwin and G. Karniadakis, A new triangular and tetrahedral basis for high-order FEM, Internat. J. Num. Meth. Engr. 38 (1995) 3775-3802
Q. Chen and I. Babuska, Approximate optimal points for polynomial interpolation of real functions in an interval and in a triangle, Comp. Meth. Appl. Mech. Engr. 128 (1995) 405-417.

There is some work on mathematical aspects of tetrahedral quadrature, e.g.,

Y. Xu, Orthogonal polynomials and cubature formulae on spheres and on simplices, Meth. Appl. Anal., to appear.
K. Gatermann, Linear representations of finite groups and the ideal theoretical construction of G-invariant cubature formulas, in T. O. Espelid, A. Genz (eds.) Numerical Integration, 25-35, Kluwer Academic Publishers, 1992.

Finally, there is a software package implementing an 8th degree rule in an adaptive (recursive) fashion to integrate over tetrahedra by

J. Berntsen, R. Cools and T. Espelid, Algorithm 720: An algorithm for automatic integration over a collection of 3-dimensional simplices, ACM Transactions on Mathematical Software, 19 (1993) 320-332.

A. Passaro, in a separate posting to NA Digest, mentions a package for exact quadrature over tetrahedra of functions arising in anisotropic finite elements, described in a paper to appear in IEEE Transactions on Magnetics.

Last updated: 8/6/98.

Stephen A. Vavasis, Computer Science Department, Cornell University, Ithaca, NY 14853, vavasis@cs.cornell.edu