Groupe d’études et de recherche en analyse des décisions

G-2003-22

Polynomial Integration Lattices

Lattice rules are quasi-Monte Carlo methods for estimating large-dimensional integrals over the unit hypercube. In this paper, after briefly reviewing key ideas of quasi-Monte Carlo methods, we give an overview of recent results, generalize them, and provide several new results, for lattice rules defined in spaces of polynomials and of formal series with coefficients in a finite ring. We discuss basic properties, implementations, a randomized version, and quality criteria (i.e., measures of uniformity) for selecting the parameters. Two types of polynomial lattice rules are examined: dimensionwise lattices and resolutionwise lattices. These rules turn out to be special cases of digital net constructions, which we reinterpret as yet another type of lattice in a space of formal series. Our development underlines the connections between integration lattices and digital nets.

, 26 pages