Qsurf: compressed QMC integration on parametric surfaces

Abstract

We discuss a “bottom-up” algorithm for Tchakaloff-like compression of QMC (QuasiMonteCarlo) integration on surfaces that admit an analytic parametrization. The key tools are Davis-Wilhelmsen theorem on the so-called “Tchakaloff sets” for positive linear functionals on polynomial spaces, and Lawson-Hanson algorithm for NNLS. This algorithm shows remarkable speed-ups with respect to Caratheodory-like subsampling, since it is able to work with much smaller matrices. We provide the corresponding Matlab code Qsurf, together with integration tests on regions of different surfaces such as sphere, torus, and a smooth Cartesian graph.