Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 

 

QMC designs: Optimal order Quasi Monte Carlo integration schemes on the sphere


Authors: J. S. Brauchart, E. B. Saff, I. H. Sloan and R. S. Womersley
Journal: Math. Comp. 83 (2014), 2821-2851
MSC (2010): Primary 65D30, 65D32; Secondary 11K38, 41A55
DOI: https://doi.org/10.1090/S0025-5718-2014-02839-1
Published electronically: April 21, 2014
MathSciNet review: 3246811
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study equal weight numerical integration, or Quasi Monte Carlo (QMC) rules, for functions in a Sobolev space $ \mathbb{H}^s( \mathbb{S}^d)$ with smoothness parameter $ s > d/2$ defined over the unit sphere $ \mathbb{S}^d$ in $ \mathbb{R}^{d+1}$. Focusing on $ N$-point configurations that achieve optimal order QMC error bounds (as is the case for efficient spherical designs), we are led to introduce the concept of QMC designs: these are sequences of $ N$-point configurations $ X_N$ on $ \mathbb{S}^d$ such that the worst-case error satisfies

$\displaystyle \sup _{\substack {f \in \mathbb{H}^s( \mathbb{S}^d ), \\ \Vert f ... ...f {x} ) \Bigg \vert = \mathcal {O}\big ( N^{-s/d} \big ), \qquad N \to \infty ,$    

with an implied constant that depends on the $ \mathbb{H}^s( \mathbb{S}^d )$-norm, but is independent of $ N$. Here $ \sigma _d$ is the normalized surface measure on $ \mathbb{S}^d$.

We provide methods for generation and numerical testing of QMC designs. An essential tool is an expression for the worst-case error in terms of a reproducing kernel for the space $ \mathbb{H}^s( \mathbb{S}^d )$ with $ s > d/2$. As a consequence of this and a recent result of Bondarenko et al. on the existence of spherical designs with appropriate number of points, we show that minimizers of the $ N$-point energy for this kernel form a sequence of QMC designs for $ \mathbb{H}^s( \mathbb{S}^d )$. Furthermore, without appealing to the Bondarenko et al. result, we prove that point sets that maximize the sum of suitable powers of the Euclidean distance between pairs of points form a sequence of QMC designs for $ \mathbb{H}^s( \mathbb{S}^d )$ with $ s$ in the interval $ {(d/2,d/2+1)}$. For such spaces there exist reproducing kernels with simple closed forms that are useful for numerical testing of optimal order Quasi Monte Carlo integration.

Numerical experiments suggest that many familiar sequences of point sets on the sphere (equal area points, spiral points, minimal [Coulomb or logarithmic] energy points, and Fekete points) are QMC designs for appropriate values of $ s$. For comparison purposes we show that configurations of random points that are independently and uniformly distributed on the sphere do not constitute QMC designs for any $ s>d/2$.

If $ (X_N)$ is a sequence of QMC designs for $ \mathbb{H}^s( \mathbb{S}^d)$, we prove that it is also a sequence of QMC designs for $ \mathbb{H}^{s'}( \mathbb{S}^d)$ for all $ s'\in (d/2,s)$. This leads to the question of determining the supremum of such $ s$ (here called the QMC strength of the sequence), for which we provide estimates based on computations for the aforementioned sequences.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65D30, 65D32, 11K38, 41A55

Retrieve articles in all journals with MSC (2010): 65D30, 65D32, 11K38, 41A55


Additional Information

J. S. Brauchart
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, NSW, 2052, Australia
Email: j.brauchart@unsw.edu.au

E. B. Saff
Affiliation: Center for Constructive Approximation, Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37240
Email: edward.b.saff@vanderbilt.edu

I. H. Sloan
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, NSW, 2052, Australia
Email: i.sloan@unsw.edu.au

R. S. Womersley
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, NSW, 2052, Australia
Email: r.womersley@unsw.edu.au

DOI: https://doi.org/10.1090/S0025-5718-2014-02839-1
Keywords: Discrepancy, spherical design, QMC design, numerical integration, quadrature, worst-case error, Quasi Monte Carlo, sphere
Received by editor(s): August 15, 2012
Received by editor(s) in revised form: February 26, 2013
Published electronically: April 21, 2014
Additional Notes: This research was supported by an Australian Research Council Discovery Project. The research of the second author was also supported by U.S. National Science Foundation grant DMS-1109266.
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.