Monthly Archives: September 2010

ICIAM2011 & MCQMC2012

ICIAM2011

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

MCQMC2012

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.

Advertisements

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