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:
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:
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. 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