Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-28T22:54:58.930Z Has data issue: false hasContentIssue false
  • English
  • Français

Constructing cubature formulae: the science behind the art

Published online by Cambridge University Press:  07 November 2008

Ronald Cools
Ronald Cools
Affiliation:
Katholieke Universiteit LeuvenDept. of Computer Science Celestijnenlaan 200A B-3001 Heverlee, Belgium E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we present a general, theoretical foundation for the construction of cubature formulae to approximate multivariate integrals. The focus is on cubature formulae that are exact for certain vector spaces of polynomials. Our main quality criteria are the algebraic and trigonometric degrees. The constructions using ideal theory and invariant theory are outlined. The known lower bounds for the number of points are surveyed and characterizations of minimal cubature formulae are given. We include references to all known minimal cubature formulae. Finally, some methods to construct cubature formulae illustrate the previously introduced concepts and theorems.

Type
Research Article
Information
Acta Numerica , Volume 6 , January 1997 , pp. 1 - 54
Copyright
Copyright © Cambridge University Press 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Appell, P. (1890), ‘Sur une classe de polynômes à deux variables et le calcul approché des intégrales double’, Ann. Fac. Sci. Univ. Toulouse 4, H1–H20.CrossRefGoogle Scholar
Appell, P. and Kampé de Fériet, J. (1926), Fonctions Hypergéométriques et Hypersphériques – Polynomes d'Hermite, Gauthier-Villars, Paris.Google Scholar
Becker, T. (1987), Konstruktion von interpolatorischen Kubaturformeln mit Anwendungen in der Finit-Element-Methode, PhD thesis, Technische Hochschule Darmstadt.Google Scholar
Beckers, M. and Cools, R. (1993), A relation between cubature formulae of trigonometric degree and lattice rules, in Numerical Integration IV (Brass, H. and Hämmerlin, G., eds), Birkhäuser, Basel, pp. 13–24.CrossRefGoogle Scholar
Beckers, M. and Haegemans, A. (1991), ‘The construction of three-dimensional invariant cubature formulae’, J. Comput. Appl. Math. 35, 109–118.CrossRefGoogle Scholar
Berens, H. and Schmid, H. J. (1992), On the number of nodes of odd degree cubature formulae for integrals with Jacobi weights on a simplex, in Numerical Integration – Recent Developments, Software and Applications (Espelid, T. and Genz, A., eds), Vol. 357 of NATO ASI Series C: Math. and Phys. Sciences, Kluwer, Dordrecht, pp. 37–44.Google Scholar
Berens, H., Schmid, H. J. and Xu, Y. (1995), ‘Multivariate Gaussian cubature formulae’, Arch. Math. 64, 26–32.CrossRefGoogle Scholar
Buchberger, B. (1985), Gröbner bases: An algorithmic method in polynomial ideal theory, in Progress, Directions and Open Problems in Multidimensional Systems Theory (Bose, N., ed.), Reidel, Dordrecht, pp. 184–232.CrossRefGoogle Scholar
Cools, R. (1989), The construction of cubature formulae using invariant theory and ideal theory, PhD thesis, Katholieke Universiteit Leuven.Google Scholar
Cools, R. (1992), A survey of methods for constructing cubature formulae, in Numerical Integration – Recent Developments, Software and Applications (Espelid, T. and Genz, A., eds), Vol. 357 of NATO ASI Series C: Math. and Phys. Sciences, Kluwer, Dordrecht, pp. 1–24.Google Scholar
Cools, R. and Haegemans, A. (1987 a), ‘Automatic computation of knots and weights of cubature formulae for circular symmetric planar regions’, J. Comput. Appl. Math. 20, 153–158.CrossRefGoogle Scholar
Cools, R. and Haegemans, A. (1987 b), ‘Construction of fully symmetric cubature formulae of degree 4K – 3 for fully symmetric planar regions’, J. Comput. Appl. Math. 17, 173–180.CrossRefGoogle Scholar
Cools, R. and Haegemans, A. (1987 c), Construction of minimal cubature formulae for the square and the triangle using invariant theory, Report TW 96, Dept. of Computer Science, Katholieke Universiteit Leuven.Google Scholar
Cools, R. and Haegemans, A. (1988 a), ‘Another step forward in searching for cubature formulae with a minimal number of knots for the square’, Computing 40, 139–146.CrossRefGoogle Scholar
Cools, R. and Haegemans, A. (1988 b), Construction of symmetric cubature formulae with the number of knots (almost) equal to Möller's lower bound, in Numerical Integration III (Brass, H. and Hämmerlin, G., eds), Birkhäuser, Basel, pp. 25–36.CrossRefGoogle Scholar
Cools, R. and Haegemans, A. (1988 c), ‘Why do so many cubature formulae have so many positive weights?’, BIT 28, 792–802.CrossRefGoogle Scholar
Cools, R. and Rabinowitz, P. (1993), ‘Monomial cubature rules since ’Stroud‘: A compilation’, J. Comput. Appl. Math. 48, 309–326.CrossRefGoogle Scholar
Cools, R. and Reztsov, A. (1997), ‘Different quality indexes for lattice rules’, J. Complexity. To appear.CrossRefGoogle Scholar
Cools, R. and Schmid, H. J. (1989), ‘Minimal cubature formulae of degree 2k – 1 for two classical functional’, Computing 43, 141–157.CrossRefGoogle Scholar
Cools, R. and Schmid, H. J. (1993), A new lower bound for the number of nodes in cubature formulae of degree 4n + 1 for some circularly symmetric integrals, in Numerical Integration IV (Brass, H. and Hämmerlin, G., eds), Birkhäuser, Basel, pp. 57–66.CrossRefGoogle Scholar
Cools, R. and Sloan, I. H. (1996), ‘Minimal cubature formulae of trigonometric degree’, Math. Comp. 65, 1583–1600.CrossRefGoogle Scholar
Davis, P. J. (1967), ‘A construction of nonnegative approximate quadratures’, Math. Comp. 21, 578–582.CrossRefGoogle Scholar
Davis, P. J. and Rabinowitz, P. (1984), Methods of Numerical Integration, Academic, London.Google Scholar
Davis, P. J., Rabinowitz, P. and Cools, R. (199x), Methods of Numerical Integration. Work in progress.Google Scholar
de Doncker, E. (1979), ‘New Euler-Maclaurin expansions and their application to quadrature over the s-dimensional simplex’, Math. Comp. 33, 1003–1018.Google Scholar
Duffy, M. G. (1982), ‘Quadrature over a pyramid or cube of integrands with a singularity at a vertex’, SIAM J. Numer. Anal. 19, 1260–1262.CrossRefGoogle Scholar
Edwards, H. M. (1980), ‘The genesis of ideal theory’, Arch. Hist. Exact Sci. 23, 321–378.CrossRefGoogle Scholar
Engels, H. (1980), Numerical Quadrature and Cubature, Academic, London.Google Scholar
Fisher, C. S. (1967), ‘The death of a mathematical theory: a study in the sociology of knowledge’, Arch. Hist. Exact Sci. 3, 136–159.Google Scholar
Flatto, L. (1978), ‘Invariants of finite reflection groups’, Enseign. Math. 24, 237–292.Google Scholar
Fritsch, F. N. (1970), ‘On the existence of regions with minimal third degree integration formulas’, Math. Comp. 24, 855–861.CrossRefGoogle Scholar
Frolov, K. K. (1977), ‘On the connection between quadrature formulas and sublattices of the lattice of integral vectors’, Soviet Math. Dokl. 18, 37–41.Google Scholar
Gatermann, K. (1988), ‘The construction of symmetric cubature formulas for the square and the triangle’, Computing 40, 229–240.CrossRefGoogle Scholar
Gatermann, K. (1992), Linear representations of finite groups and the ideal theoretical construction of G-invariant cubature formulas, in Numerical Integration – Recent Developments, Software and Applications (Espelid, T. and Genz, A., ), Vol. 357 of NATO ASI Series C: Math. and Phys. Sciences, Kluwer, Dordrecht, pp. 25–35.Google Scholar
Gebauer, R. and Möller, H. M. (1988), ‘On an installation of Buchberger's algorithm’, J. Symb. Computation 6, 275–286.CrossRefGoogle Scholar
Gout, J. L. and Guessab, A. (1986), ‘Sur les formules de quadrature numérique à nombre minimal de noeuds d'intégration’, Numer. Math. 49, 439–455.CrossRefGoogle Scholar
Gröbner, W. (1949), Moderne Algebraische Geometrie, Springer, Wien.CrossRefGoogle Scholar
Grundmann, A. and Möller, H. M. (1978), ‘Invariant integration formulas for the n-simplex by combinatorial methods’, SIAM J. Numer. Anal. 15, 282–290.CrossRefGoogle Scholar
Guessab, A. (1986), ‘Cubature formulae which are exact on spaces P, intermediate between Pk and Qk’ Numer. Math. 49, 561–576.CrossRefGoogle Scholar
Haegemans, A. (1982), Construction of known and new cubature formulas of degree five for three-dimensional symmetric regions, using orthogonal polynomials, in Numerical Integration, Birkhäuser, Basel, pp. 119–127.CrossRefGoogle Scholar
Haegemans, A. and Piessens, R. (1976), ‘Construction of cubature formulas of degree eleven for symmetric planar regions, using orthogonal polynomials’, Numer. Math. 25, 139–148.CrossRefGoogle Scholar
Haegemans, A. and Piessens, R. (1977), ‘Construction of cubature formulas of degree seven and nine symmetric planar regions, using orthogonal polynomials’, SIAM J. Numer. Anal. 14, 492–508.CrossRefGoogle Scholar
Hilbert, D. (1890), ‘Über die Theorie der algebraischen Formen’, Math. Ann. 36, 473–534.CrossRefGoogle Scholar
Hillion, P. (1977), ‘Numerical integration on a triangle’, Internat. J. Numer. Methods Engrg. 11, 797–815.CrossRefGoogle Scholar
Jackson, D. (1936), ‘Formal properties of orthogonal polynomials in two variables’, Duke Math. J. 2, 423–434.CrossRefGoogle Scholar
Keast, P. and Lyness, J. N. (1979), ‘On the structure of fully symmetric multidimensional quadrature rules’, SIAM. J. Numer. Anal. 16, 11–29.CrossRefGoogle Scholar
Kepler, J. (1615), Nova stereometria doliorum vinariorum, in primis Austriaci, figuræ omnium aptissimæ, Authore Ioanne Kepplero, imp. Cæs. Matthiæ I. ejusq; fidd. Ordd. Austriæ supra Anasum Mathematico, Lincii, Anno MDCXV.Google Scholar
Konjaev, S. I. (1977), ‘Ninth-order quadrature formulas invariant with respect to the icosahedral group’, Soviet Math. Dokl. 18, 497–501.Google Scholar
Korobov, N. M. (1959), ‘On approximate calculation of multiple integrals’, Dokl. Akad. Nauk SSSR 124, 1207–1210. Russian.Google Scholar
Lebedev, V. I. (1976), ‘Quadrature on a sphere’, USSR Comput. Math. and Math. Phys. 16, 10–24.CrossRefGoogle Scholar
Lebedev, V. I. (1995), ‘A quadrature formula for the sphere of 59th algebraic order of accuracy’, Dokl. Math. 50, 283–286.Google Scholar
Lebedev, V. I. and Skorokhodov, A. L. (1992), ‘Quadrature formulas of orders 41, 47, and 53 for the sphere’, Dokl. Math. 45, 587–592.Google Scholar
Li, T. Y. (1997), Numerical solution of multivariate polynomial systems by homotopy continuation methods, in Acta Numerica, Vol. 6, Cambridge University Press, pp. 399–436.Google Scholar
Lyness, J. N. (1976), ‘An error functional expansion for N-dimensional quadrature with an integrand function singular at a point’, Math. Comp. 30, 1–23.Google Scholar
Lyness, J. N. (1992), On handling singularities in finite elements, in Numerical Integration – Recent Developments, Software and Applications (Espelid, T. and Genz, A., eds), Vol. 357 of NATO ASI Series C: Math. and Phys. Sciences, Kluwer, Dordrecht, pp. 219–233.Google Scholar
Lyness, J. N. and Cools, R. (1994), A survey of numerical cubature over triangles, in Mathematics of Computation 1943–1993: A Half-Century of Computational Mathematics (Gautschi, W., ed.), Vol. 48 of Proceedings of Symposia in Applied Mathematics, AMS, Providence, RI, pp. 127–150.CrossRefGoogle Scholar
Lyness, J. N. and de Doncker, E. (1993), ‘Quadrature error expansions, II. The full corner singularity’, Numer. Math. 64, 355–370.CrossRefGoogle Scholar
Lyness, J. N. and de Doncker-Kapenga, E. (1987), ‘On quadrature error expansions, part I’, J. Comput. Appl. Math. 17, 131–149.CrossRefGoogle Scholar
Lyness, J. N. and Jespersen, D. (1975), ‘Moderate degree symmetric quadrature rules for the triangle’, J. Inst. Math. Appl. 15, 19–32.CrossRefGoogle Scholar
Lyness, J. N. and McHugh, B. J. J. (1970), ‘On the remainder term in the N-dimensional Euler-Maclaurin expansion’, Numer. Math. 15, 333–344.CrossRefGoogle Scholar
Lyness, J. N. and Monegato, G. (1980), ‘Quadrature error functional expansion for the simplex when the integrand has singularities at vertices’, Math. Comp. 34, 213–225.CrossRefGoogle Scholar
Lyness, J. N. and Puri, K. K. (1973), ‘The Euler-Maclaurin expansion for the simplex’, Math. Comp. 27, 273–293.CrossRefGoogle Scholar
Maeztu, J. I. and Sainz de la Maza, E. (1995), ‘Consistent structures of invariant quadrature rules for the n-simplex’, Math. Comp. 64, 1171–1192.Google Scholar
Mantel, F. and Rabinowitz, P. (1977), ‘The application of integer programming to the computation of fully symmetric integration formulas in two and three dimensions’, SIAM J. Numer. Anal. 14, 391–425.CrossRefGoogle Scholar
Maxwell, J. C. (1877), ‘On approximate multiple integration between limits of summation’, Proc. Cambridge Philos. Soc. 3, 39–47.Google Scholar
Möller, H. M. (1973), Polynomideale und Kubaturformeln, PhD thesis, Universität Dortmund.Google Scholar
Möller, H. M. (1976), ‘Kubaturformeln mit minimaler Knotenzahl’, Numer. Math. 25, 185–200.CrossRefGoogle Scholar
M, H. M.öller (1979), Lower bounds for the number of nodes in cubature formulae, in Numerische Integration, Vol. 45 of ISNM, Birkhäuser, Basel, pp. 221–230.Google Scholar
Möller, H. M. (1987), On the construction of cubature formulae with few nodes using Gröbner bases, in Numerical Integration (Keast, P. and Fairweather, G., eds), Reidel, Dordrecht, pp. 177–192.CrossRefGoogle Scholar
Möller, H. M. and Mora, F. (1986), ‘New constructive methods in classical ideal theory’, J. Algebra 100, 138–178.CrossRefGoogle Scholar
Morrow, C. R. and Patterson, T. N. L. (1978), ‘Construction of algebraic cubature rules using polynomial ideal theory’, SIAM J. Numer. Anal. 15, 953–976.CrossRefGoogle Scholar
Mysovskikh, I. P. (1966), ‘A proof of minimality of the number of nodes of a cubature formula for a hypersphere’, Zh. Vychisl. Mat. Mat. Fiz. 6, 621–630. Russian. Published as I. P. Mysovskih 1966.Google Scholar
Mysovskikh, I. P. (1968), ‘On the construction of cubature formulas with fewest nodes’, Soviet Math. Dokl. 9, 277–280.Google Scholar
Mysovskikh, I. P. (1975), ‘On Chakalov's theorem’, USSR Comput. Math. and Math. Phys. 15, 221–227.CrossRefGoogle Scholar
Mysovskikh, I. P. (1977), ‘On the evaluation of integrals over the surface of a sphere’, Soviet Math. Dokl. 18, 925–929. Published as I. P. Mysovskih 1977.Google Scholar
Mysovskikh, I. P. (1980), The approximation of multiple integrals by using interpolatory cubature formulae, in Quantitative Approximation (Vore, R. D. and Scherer, K., eds), Academic, New York, pp. 217–243.CrossRefGoogle Scholar
Mysovskikh, I. P. (1981), Interpolatory Cubature Formulas, Izdat. ‘Nauka’, Moscow-Leningrad. Russian. See I. P. Mysovskikh 1992.Google Scholar
Mysovskikh, I. P. (1988), ‘Cubature formulas that are exact for trigonometric polynomials’, Metody Vychisl. 15, 7–19. Russian.Google Scholar
Mysovskikh, I. P. (1990), On the construction of cubature formulas that are exact for trigonometric polynomials, in Numerical Analysis and Mathematical Modelling (Wakulicz, A., ed.), Vol. 24 of Banach Center Publications, PWN – Polish Scientific Publishers, Warsaw, pp. 29–38. Russian.Google Scholar
Mysovskikh, I. P. (1992), Interpolatorische Kubaturformeln, Bericht Nr. 74, Institut für Geometrie und Praktische Mathematik der RWTH Aachen. Translated from the Russian by Dietrich, I. and Engels, H.. Published as J. P. Mysovskih 1992.Google Scholar
Mysovskikh, I. P. and Ja Černicina, V. (1971), ‘The answer to a question of Radon’, Soviet Math. Dokl. 12, 852–854. Published as I. P. Mysovskih and V. Ja Černicina 1971.Google Scholar
Niederreiter, H. (1992), Random Number Generation and Quasi-Monte Carlo Methods, Vol. 63 of CBMS-NSF regional conference series in applied mathematics, SIAM, Philadelphia.CrossRefGoogle Scholar
Noskov, M. V. (1988 a), ‘Cubature formulae for the approximate integration of functions of three variables’, USSR Comput. Math. and Math. Phys. 28, 200–202.CrossRefGoogle Scholar
Noskov, M. V. (1988 b), ‘Formulas for the approximate integration of periodic functions’, Metody Vychisl. 15, 19–22. Russian.Google Scholar
Piessens, R. and Haegemans, A. (1975), ‘Cubature formulas of degree nine for symmetric planar regions’, Math. Comp. 29, 810–815.CrossRefGoogle Scholar
Rabinowitz, P. and Richter, N. (1969), ‘Perfectly symmetric two-dimensional integration formulas with minimal number of points’, Math. Comp. 23, 765–799.CrossRefGoogle Scholar
Radon, J. (1948), ‘Zur mechanischen Kubatur’, Monatsh. Math. 52, 286–300.CrossRefGoogle Scholar
Rasputin, G. G. (1983 a), ‘On the construction of cubature formulas containing prespecified knots’, Metody Vychisl. 13, 122–128. Russian.Google Scholar
Rasputin, G. G. (1983 b), ‘On the question of numerical characteristics for orthogonal polynomials of two variables’, Metody Vychisl. 13, 145–154. Russian.Google Scholar
Rasputin, G. G. (1986), ‘Construction of cubature formulas containing preassigned nodes’, Soviet Math. (Iz. VUZ) 30, 58–67.Google Scholar
Richardson, L. F. (1927), ‘The deferred approach to the limit’, Philos. Trans. Royal Soc. London 226, 261–299.Google Scholar
Richtmyer, R. D. (1952), The evaluation of definite integrals, and a quasi-Monte-Carlo method based on the properties of algebraic numbers, Report LA-1342, Los Alamos Scientific Laboratory.CrossRefGoogle Scholar
Schmid, H. J. (1978), ‘On cubature formulae with a minimal number of knots’, Numer. Math. 31, 281–297.CrossRefGoogle Scholar
Schmid, H. J. (1980 a), ‘Interpolatorische Kubaturformeln und reelle Ideale’, Math. Z. 170, 267–282.CrossRefGoogle Scholar
Schmid, H. J. (1980 b), Interpolatory cubature formulae and real ideals, in Quantitative Approximation (Vore, R. D. and Scherer, K., eds), Academic, New York, pp. 245–254.CrossRefGoogle Scholar
Schmid, H. J. (1983), Interpolatorische Kubaturformeln, Vol. CCXX of Dissertationes Math., Polish Scientific Publishers, Warsaw.Google Scholar
Schmid, H. J. (1995), ‘Two-dimensional minimal cubature formulas and matrix equations’, SIAM J. Matrix Anal. 16(3), 898–921.CrossRefGoogle Scholar
Schmid, H. J. and Xu, Y. (1994), ‘On bivariate Gaussian cubature formulae’, Proc. Amer. Math. Soc. 122, 833–842.CrossRefGoogle Scholar
Sloan, I. H. and Joe, S. (1994), Lattice Methods for Multiple Integration, Oxford University Press.CrossRefGoogle Scholar
Sloan, I. H. and Kachoyan, P. J. (1987), ‘Lattice mathods for multiple integration: theory, error analysis and examples’, SIAM J. Numer. Anal. 24, 116–128.CrossRefGoogle Scholar
Sobolev, S. L. (1962), ‘The formulas of mechanical cubature on the surface of a sphere’, Sibirsk. Mat. Zž. 3, 769–796. Russian.Google Scholar
Stroud, A. H. (1960), ‘Quadrature methods for functions of more than one variable’, New York Acad. Sci. 86, 776–791.CrossRefGoogle Scholar
Stroud, A. H. (1971), Approximate calculation of multiple integrals, Prentice-Hall, Englewood Cliffs, NJ.Google Scholar
Sturmfels, B. (1996), Gröbner Bases and Convex Polytopes, Vol. 8 of University Lecture Series, AMS, Providence, RI.Google Scholar
Taylor, M. (1995), ‘Cubature for the sphere and the discrete spherical harmonic transform’, SIAM J. Numer. Anal. 32(2), 667–670.CrossRefGoogle Scholar
Tchakaloff, V. (1957), ‘Formules de cubatures mécaniques à coefficients non négatifs’, Bull. des Sciences Math., 2e série 81, 123–134.Google Scholar
Verlinden, P. and Cools, R. (1992), ‘On cubature formulae of degree 4k + 1 attaining Möller's lower bound for integrals with circular symmetry’, Numer. Math. 61, 395–407.CrossRefGoogle Scholar
Verlinden, P. and Haegemans, A. (1993), ‘An error expansion for cubature with an integrand with homogeneous boundary singularities’, Numer. Math. 65, 383–406.CrossRefGoogle Scholar
Wei, S.ß (1991), Über Kubaturformeln vom Grad 2k – 2, Master's thesis, Universität Erlangen.Google Scholar
Wissman, J. W. and Becker, T. (1986), ‘Partially symmetric cubature formulas for even degrees of exactness’, SIAM J. Numer. Anal. 23, 676–685.CrossRefGoogle Scholar