Computational Higher Order Quasi-Monte Carlo Integration

Abstract

The efficient construction of higher-order interlaced polynomial lattice rules introduced recently in [4] is considered. After briefly reviewing the principles of their construction by the “fast component-by-component” (CBC) algorithm due to [1, 10] as well as recent theoretical results on their convergence rates, we indicate algorithmic details of their construction. Instances of such rules are applied to highdimensional test integrands which belong to weighted function spaces with weights of product and of SPOD type. Practical considerations that lead to improved quantitative convergence behavior for various classes of test integrands are reported. The use of (analytic or numerical) bounds on theWalsh coefficients of the integrand are found to improve the convergence behavior. The sharpness of theoretical bounds on memory usage and operation counts, with respect to the number of points N and dimension s of the integration domain is verified experimentally. The efficiency of the proposed algorithms for computation of the generating vectors is confirmed for the considered classes of functions in dimensions s = 10, ...,1000.