Monthly Archives: January 2010

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

Consistency of Markov Chain quasi-Monte Carlo for continuous state spaces

This post is based on the paper

and my previous talks on this topic at the UNSW statistic seminar and the Dagstuhl Workshop in 2009. The slides of my talk at Dagstuhl can be found here. I give an illustration of the results rather than rigorous proofs, which can be found in the paper [CDO].

The classical paper on this topic is by [Chentsov 1967]:

N. N. Chentsov, Pseudorandom numbers for modelling Markov chains, Computational Mathematics and Mathematical Physics, 7, 218–2332, 1967.

Further important steps were taken by A. Owen and S. Tribble, see doi: 10.1073/pnas.0409596102 and doi: 10.1214/07-EJS162. Recent papers of interest in this context are also by A. Hinrichs doi:10.1016/j.jco.2009.11.003, and D. Rudolf doi: 10.1016/j.jco.2008.05.005. The slides of the presentations at Dagstuhl of Hinrichs can be found here here and of Rudolf can be found here.

1. Introduction

The task is to approximate an integral Continue reading

ICIAM 2011 Minisymposia

Steffen Dereich, Michael Gnewuch, Anargyros Papageorgiou, and myself will organise minisymposia at the ICIAM 2011 conference in Vancouver. This conference will be held from July 18 to 22, 2011.

The aim is to establish an organised platform for our colleagues to give and attend talks which are broadly related to each other. Topics discussed at previous conferences can be found at the Dagstuhl homepage, the MCQMC 2010 conference, the FOCM’08 conference, the Uniform Distribution Theory conference, the Discrepancy Workshop in Varenna, and others (this list is of course biased and not complete). In effect we will have our own miniconference within ICIAM by arranging a series of minisymposia. I may point out though that none of the above mentioned including myself is in any way part of the ICIAM conference organisation itself.

Continue reading

Exponential Convergence and Tractability of Multivariate Integration for Korobov Spaces

I discuss the recently resubmitted manuscript [DLPW] titled `Exponential Convergence and Tractability of Multivariate Integration for Korobov Spaces‘ by J.D., G. Larcher, F. Pillichshammer, and H. Wo\’zniakowski.

The initial aim of the paper is to show that lattice rules can achieve an exponential rate of convergence for infinitely times differentiable functions. The technical difficulty therein lies in the fact that an application of Jensen’s inequality (which states that {(\sum_{n} |a_n|)^\lambda \le \sum_n |a_n|^\lambda} for {0 < \lambda < 1}) yields only a convergence of {O(n^{-\alpha})}, where {n} is the number of quadrature points. Though {\alpha} can be arbitrarily large, in the land of asymptotia this is still worse than a convergence of, say, {\omega^{-n^{1/s}}}, for some {0 < \omega < 1}. Hence the first challenge is to find ways to prove convergence rates without relying on Jensen’s inequality.

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