Tag Archives: Higher order digital net

Digital Nets and Sequences Preprint

A complete preprint of the book

is now available here. The final published version can be obtained directly from Cambridge University Press here.

The preprint version differs of course from the final version, for instance, the page numbers are different. However, the numbering of Chapters, Sections, Theorems, Lemmas, Corollaries, Definitions and Examples is the same in both versions. The list of corrections is for the published version. We do not have a separate list for the preprint version (though the corrections for the published version also apply to the preprint version).

Advertisements

Higher order nets and a higher order Sudoku

In the following we first describe a connection of (t,m,s)-nets and Sudoku and then generalize the Sudoku in analogy to higher order (t,\alpha, \beta, m, n, s)-nets in base 3. A new type of Sudoku puzzle is presented at the end. Continue reading

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

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

How to generate higher order Sobol points in Matlab and some numerical examples

Higher order digital nets and sequences are quasi-Monte Carlo point sets \{\boldsymbol{x}_{n-1}\}_{n=1}^N, where N=b^m for digital nets and N=\infty for digital sequences (for more background information on this topic see Chapters 1-4 and Chapter 8 in the book; several sample chapters of this book can be downloaded here), which satisfy the following property:

\displaystyle \left|\int_{[0,1]^s} f(\boldsymbol{x}) \, \mathrm{d} \boldsymbol{x}  -  \frac{1}{b^m} \sum_{n=0}^{b^m-1} f(\boldsymbol{x}_n) \right|  \le C_{s,\alpha} \frac{(\log N)^{s \alpha}}{N^\alpha}, \hspace{2cm} (1)

where \alpha \ge 1 is the smoothness of the integrand {}f and C_{s,\alpha} \textgreater 0 is a constant which only depends on {}s and {}\alpha (but not on {}N). For instance, if {}f has square integrable partial mixed derivatives up to order {}2 in each variable, then we get a convergence rate of \mathcal{O}(N^{-2+\varepsilon}), where {}N is the number of quadrature points used in the approximation and \varepsilon >0 can be chosen arbitrarily small. If {}f has {}3 derivatives then we get a convergence of \mathcal{O}(N^{-3+\varepsilon}), and so on.

This method has been introduced in the papers:

The first paper only deals with periodic functions, whereas the second paper also includes nonperiodic functions.

For some heuristic explanation how higher order digital nets and sequences work see the paper:

  • J. Dick, On quasi-Monte Carlo rules achieving higher order convergence. In: Proceedings of the MCQMC’08 conference, Montreal, Canada, P. L’Ecuyer and A. Owen (eds.), pp. 73–96, 2009. doi: 10.1007/978-3-642-04107-5_5 An earlier version can be found here.

In this entry we provide a Matlab program which generates point sets which satisfy the property (1). 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

Duality Theory and Propagation Rules for Higher Order Nets

We (J. Baldeaux, J.D., F. Pillichshammer) just submitted a manuscript on Duality Theory and Propagation Rules for Higher Order Nets (you can download the manuscript by clicking on the title). In a nutshell, propagation rules are methods to construct, from given nets with some given parameters, new nets with at least one parameter different from the given nets. Duality theory on the other hand is the vehicle which allows us to analyse those propagation rules. It is an analytic description (using Walsh functions in our case) of the geometric properties of nets.

The manuscript is a continuation of the paper with P. Kritzer on Duality Theory and Propagation Rules for Generalized Digital Nets [44]. (Note that in some papers the notion `generalized (digital) net’ was used instead of the term `(digital) higher order net’.) The difference is that we do not assume that the point sets are constructed by the digital construction scheme.

Most propagation rules for classical {(t,m,s)}-nets have a higher order analogue. This applies to digital as well as geometric nets. Additionally there are also some further propagation rules which do not exist for classical nets (for example the higher order to higher order construction). The higher order to higher order propagation rule is, as of now, still the only method to obtain higher order nets from classical nets. Fortunately it works in the digital as well as geometric case.

1. A subnet propagation rule for digital higher order nets

We give an example of a propagation rule in the following. In the classical case there is a propagation rule which states that: Continue reading