Category Archives: Open problems

Some possible simplifications of the notation of higher order nets and sequences

In this entry I discuss the definition of (digital) higher order nets and sequences and some possible simplifications of the notation.

Digital higher order nets and sequences have been introduced in

whereas higher order nets have been introduced in

  • [2] J. Dick and J. Baldeaux, Equidistribution properties of generalized nets and sequences. In: Proceedings of the MCQMC’08 conference, Montreal, Canada, P. L’Ecuyer and A. Owen (eds.), pp. 305–323, 2009. doi: 10.1007/978-3-642-04107-5_19 An earlier version can be found here.

There are several parameters occurring in the definition of higher order nets, namely t, \alpha,\beta, n, m, s, b and for higher order sequences we have the parameters t, \alpha, \beta, \sigma, s, b.

(Digital) higher order nets and sequences are point sets \{\boldsymbol{x}_0,\ldots, \boldsymbol{x}_{b^m-1}\} \subset [0,1)^s and sequences \{\boldsymbol{x}_0,\boldsymbol{x}_1, \ldots, \} such that

\displaystyle \left|\int_{[0,1]^s} f(\boldsymbol{x}) \,\mathrm{d} \boldsymbol{x} - \frac{1}{N} \sum_{n=0}^{N-1} f(\boldsymbol{x}_n) \right| = \mathcal{O} (N^{-\alpha} (\log N)^{\alpha s}),

where {}N =b^m is the number of quadrature points and {} \alpha is the smoothness of the integrand {}f. Continue reading

Advertisements

Open internet project 1: Lattice rules for R^s

In this post I describe an approach for constructing lattice rules which might be useful for integration in \mathbb{R}^s. The aim is to use the main ideas from the construction of digital nets over \mathbb{R}^s, see here, and apply them to lattice rules. This is the first project mentioned here. Continue reading

Higher order scrambling

Recently I uploaded the paper

This paper deals with a generalization of Owen’s scrambling algorithm which improves on the convergence rate of the root mean square error for smooth integrands. The bound on the root mean square error is best possible (apart from the power of the \log N factor) and this can also be observed from some simple numerical examples shown in the paper (note that the figures in the paper show the standard deviation (or root mean square error) and not the variance of the estimator). In this post you can also find Matlab programs which generate the quadrature points introduced in this paper and a program to generate the numerical results shown in the paper. Continue reading

The connection between the logarithmic Walsh degree of exactness, the t value of digital nets and an idea for future research

In this entry we show how the Walsh degree of a digital net is connected to its t value. This can lead to future research by using ideas developed for finding lattice rules with large trigonometric degree. Continue reading

Construction Algorithms for Higher Order Polynomial Lattice Rules

We recently submitted the manuscript

This paper fits into the work on higher order quasi-Monte Carlo rules which started with [22] and [31]. It can be viewed as the higher order extension of [7], where classical polynomial lattice rules were considered.

1. Construction Algorithms

As stated in the title of the manuscript, we present construction algorithms for higher order polynomial lattice rules. The construction is based on the worst-case error rather than the quality parameter {t}. This allows us to find good higher order polynomial lattice rules for weighted function spaces. It also presents a feasible alternative to the direct construction introduced in [31] (and [22] for the periodic case).

We use a variety of approaches to achieve our results. Continue reading

On the fast component-by-component algorithm for polynomial lattice rules

We present some simplification and observations concerning the fast component-by-component algorithm for polynomial lattice rules. This algorithm was introduced by Nuyens and Cools in

D. Nuyens and R. Cools. Fast component-by-component construction, a reprise for different kernels. In H. Niederreiter and D. Talay, editors, Monte Carlo and Quasi-Monte Carlo Methods 2004, pages 371–385. Springer-Verlag, 2006. Cited on pp. 82, 153, 178. See also Chapter 6 of Dirk’s PhD Thesis.

Let {\boldsymbol{x} = (x_1,\ldots, x_s)} and {x_i = \xi_{i,1} b^{-1} + \xi_{i,2} b^{-2} + \cdots} be the {b} adic expansion of {x} (unique in the sense that infinitely many of the {\xi_{i,j}} are different from {b-1}). We use the notation as in the book. Assume that {b} is a prime number. For the sake of definiteness, consider the mean square worst-case error Continue reading