ICIAM2011 & MCQMC2012


The next ICIAM conference is held in Vancouver from 18th to 22nd of July 2011. Jan Baldeaux, Michael Gnewuch, Anargyros Papageorgiou and myself are going to propose several mini-symposia on Approximation, Tractability, Discrepancy theory and Applications of Monte Carlo and quasi-Monte Carlo methods. Currently we have 15 speakers. If you would like to join one of our mini-symposia please send me an email well before the 18th of October (which is the deadline for proposing mini-symposia).


The tenth international conference on Monte Carlo and quasi-Monte Carlo conference (MCQMC) will be held at UNSW in Sydney from 13th to 17th of February 2012. The official website can be found here. More information will be posted there in due course.

Korobov discovered the component-by-component construction of lattice rules in 1959

Alexey Ustinov recently pointed out that Korobov invented the component-by-component construction of lattice rules in 1959. He provided two references for this result, namely

  • @article {MR0104086,
        AUTHOR = {Korobov, N. M.},
         TITLE = {Approximate evaluation of repeated integrals},
       JOURNAL = {Dokl. Akad. Nauk SSSR},
      FJOURNAL = {Doklady Akademii Nauk SSSR},
        VOLUME = {124},
          YEAR = {1959},
         PAGES = {1207–1210},
  • Theorem 18 on page 120 in Korobov’s book from 1963:

    @book {MR0157483,
    AUTHOR = {Korobov, N. M.},
    TITLE = {Teoretiko-chislovye metody v priblizhennom analize},
    PUBLISHER = {Gosudarstv. Izdat. Fiz.-Mat. Lit., Moscow},
    YEAR = {1963},
    PAGES = {224},

In this post I provide a (rough) translation of the results of Korobov (I do not know Russian, so I only understand the formulae). Indeed, as can be seen below, Korobov used the algorithm which is now called component-by-component construction (and which was re-invented much later by Sloan and Reztsov in Sloan, I. H.; Reztsov, A. V. Component-by-component construction of good lattice rules. Math. Comp. 71 (2002), no. 237, 263–273). He also proved that lattice rules constructed component-by-component achieve the optimal rate of convergence of the integration error for functions in the class E^\alpha_s (i.e., he showed that P_\alpha = \mathcal{O}(p^{-\alpha} (\ln p)^{\alpha s}) where {}p is the number of quadrature points).

Unfortunately many authors were not aware of Korobov’s result, hence Korobov has not received due credit for this result. To rectify this situation somewhat (and help make authors aware of Korobov’s result), we provide the details of Korobov’s result here. 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

Walsh functions III: The convergence of the Walsh coefficients and pointwise convergence

In a previous post, we discussed the orthogonality properties of Walsh functions and showed that they form a complete orthonormal system in L_2([0,1]). In this post we discuss the rate of decay of the Walsh coefficients when the function has bounded variation of fractional order 0 \textless \alpha \le 1 and we investigate pointwise convergence of the Walsh series and pointwise convergence of the Walsh series to the function. We consider only Walsh functions in base 2, although the results can be generalized to Walsh functions over groups. Information on Walsh functions over groups can be found in this post. For the necessary background information see the previous post on Walsh functions here. A table of contents for the posts on Walsh functions can be found 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

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

Walsh functions II: Walsh functions in general base and Walsh functions over groups

In a previous post we introduced Walsh functions. We showed that this set of functions is orthogonal and complete. In this post we generalize the Walsh function system such that the orthonormality and completeness of the new Walsh function system still holds. A table of contents for the posts on Walsh functions can be found here. Continue reading