Fast Component-by-Component Construction, a Reprise for Different Kernels

Dirk Nuyens () and Ronald Cools ()
Additional contact information
Dirk Nuyens: K.U.Leuven, Dept. of Computer Science
Ronald Cools: K.U.Leuven, Dept. of Computer Science

A chapter in Monte Carlo and Quasi-Monte Carlo Methods 2004, 2006, pp 373-387 from Springer

Abstract: Summary In [16] (Nuyens and Cools) it was shown that it is possible to generate rank-1 lattice rules with n points, n being prime, in a fast way. The construction cost in shift-invariant tensor-product reproducing kernel Hilbert spaces was reduced from O(sn 2) to O(sn log(n)), with s the number of dimensions. This reduction in construction cost was made possible by exploiting the algebraic structure of multiplication modulo a prime. Here we look at the applications of the fast algorithm from a practical point of view. Although the choices for the function space are arbitrary, in practice only few kernels are used for the construction of rank-1 lattices. We will discuss componentby-component construction for the worst-case Korobov space, the average-case Sobolev space, the weighted lattice criterion R n,γ and polynomial lattice rules based on the digital Walsh kernel, of which the last two were presented at MC2QMC 2004 by Joe [11] and Dick, Leobacher and Pillichshammer, see e.g. [7]. We also give an example implementation of the algorithm in Matlab.

Keywords: Numerical integration; Quasi-Monte Carlo; Rank-1 lattice rules; Component-by-component construction; Fast algorithms; Digital nets (search for similar items in EconPapers)
Date: 2006
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-31186-7_22

Ordering information: This item can be ordered from
http://www.springer.com/9783540311867

DOI: 10.1007/3-540-31186-6_22

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().