Tag Archives: quasi-Monte Carlo

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).

QMC rules over R^s: Matlab code and numerical example

In this post you can find a Matlab code for constructing digital nets on \mathbb{R}^s which was recently proposed in J. Dick, Quasi-Monte Carlo numerical integration on \mathbb{R}^s: digital nets and worst-case error. Submitted, 2010. See the previous post where an explanation of the method and a link to the paper can be found. In the numerical example we consider a simple three-dimensional integral. In this example the computation time with the new method is reduced by a factor of ten and additionally the integration error is also reduced. The numerical result in the paper shows that, for the example considered there, that the computation time can be reduced from two and a half minutes to less than two seconds for a certain given error level. Continue reading

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

A Construction of Polynomial Lattice Rules with Small Gain Coefficients

Recently J. Baldeaux and myself submitted the manuscript titled A Construction of Polynomial Lattice Rules with Small Gain Coefficients.

In this paper we construct polynomial lattice rules which have, in some sense, small gain coefficients using a component-by-component approach. The gain coefficients, as introduced by Art Owen, indicate to what degree the method improves upon Monte Carlo. We show that the variance of an estimator based on a scrambled polynomial lattice rule constructed component-by-component decays at a rate of N^{-(2\alpha + 1) +\delta}, for all \delta >0, assuming that the function under consideration bounded fractional variation of order \alpha and where N denotes the number of quadrature points. We give some further comments on the paper. Continue reading

Quasi-Monte Carlo for R^s: digital nets and worst-case error

Recently I submitted the paper titled Quasi-Monte Carlo numerical integration over \mathbb{R}^s: digital nets and worst-case error. I will give some heuristic explanation of the results in this paper. Interesting in this context is also the sparse grid approach from the PhD thesis of Markus Holtz (supervised by Prof. Michael Griebel).

Therein I aim to develop a theory on quasi-Monte Carlo integration over \mathbb{R}^s. The idea is to transform a digital net from [0,1]^s to \mathbb{R}^s such that in elementary intervals of the form \displaystyle \prod_{i=1}^s [A b^j, (A+1) b^j) one has a digitally shifted digital net, and at the same time, globally one has a given (discretized) distribution. 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

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