File(s) not publicly available
A component-by-component approach to efficient numerical integration over products of spheres
journal contribution
posted on 2023-06-07, 21:43 authored by Kerstin Hesse, Frances Y Kuo, Ian H SloanBuilding upon a recent existence result of Kuo and Sloan, this paper presents a component-by-component algorithm for constructing the $m$ points of a quasi-Monte Carlo (QMC) rule for numerical integration over the $d$-fold product of unit spheres $S^2\\subset\\mathbb{R}^3$. Our construction is as follows: starting with a well chosen generating point set of $m$ points on $S^2$, the algorithm chooses a permutation of this generating point set for each sphere, one sphere at a time, so that the projection of the $m$ QMC points onto each sphere is the same, and is just the generating point set but with the points occurring in a different order. Understandably, the quality of our QMC rule depends on the quality of both the generating point set and the successive permutations. This paper contains two key results. Firstly, assuming that the worst-case error for the generating point set in a certain Sobolev space satisfies a certain estimate, we prove inductively that the resulting QMC rule satisfies the existence result for the worst-case error bound in a $d$-dimensional weighted Sobolev space established non-constructively by Kuo and Sloan: specifically, the worst-case error of our QMC rule is bounded from above by $c m^{-1/2}$, where $c>0$ is independent of $m$ and $d$, provided that the sum of the weights is bounded independently of $d$. Secondly, we show that the desired estimate for the generating point set on $S^2$ is automatically satisfied for $m$ sufficiently large by a spherical $n$-design with $m=O(n^2)$ points (if such spherical designs exist) and by a spherical $n$-design with $m=O(n^3)$ points if slightly stronger assumptions are made on the smoothness of the weighted function space. The latter task involves techniques developed by Hesse and Sloan for numerical integration in Sobolev spaces on $S^2$. The construction cost for the component-by-component algorithm grows only linearly with $d$. However, a complete search over all $m!$ permutations at each step of the construction is infeasible, thus a randomized version of the algorithm is recommended in practice.
History
Publication status
- Published
Journal
Journal of ComplexityISSN
0885-064XExternal DOI
Issue
1Volume
23Page range
25-51Pages
27.0Department affiliated with
- Mathematics Publications
Full text available
- No
Peer reviewed?
- Yes
Legacy Posted Date
2012-02-06Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC