Title: A generic lattice sequences library for numerical integration Authors: Nuyens, Dirk # × Issue Date: Jul-2008 Conference: Biennial Computational Techniques and Applications Conference (CTAC) edition:2008 location:Australian National University (ANU), Canberra, Australia date:13-16 July 2008 Abstract: We present an overview on how to implement the very simple formula for the generation of (rank-$1$) lattice rule points $\mathbf{x}_k = \frac{k \mathbf{z} \bmod{n}}{n} , \qquad 0 \le k < n , \quad \mathbf{z} \in \mathbb{Z}_n^s .$ These point sets are used for the approximation of $s$-dimensional integrals by the equal-weight cubature rule $\frac{1}{n} \sum_{k=0}^{n} f(\mathbf{x}_k) \approx \int_{[0,1)^s} f(\mathbf{x}) \,\mathrm{d}\mathbf{x} .$ Especially in high dimensions, say $s > 100$, lattice rules are an important numerical technique for the approximation of multi-variate integrals, e.g., in mathematical finance. Previous work by the author involve fast algorithms to construct good generating vectors $\mathbf{z}$ for various kinds of lattice rules. In its most general form we consider lattice rules with point sets generated as $\mathbf{x}_k = \tau( \varphi(k) \mathbf{z} ) .$ Hereby is $\varphi(k) \mathbf{z}$ a multiple of the generating vector $\mathbf{z}$ under the operation of a quotient r ing $R$, $\tau$ a mapping from the lattice to the $s$-dimensional integration domain $[0,1)^s$ and $\varphi$ a well chosen permutation to be able to use the lattice rule as a sequence. The aim of the implementation is for both efficiency and mathematical abstraction. That is: we want to be able to capture the most simple form of a (fixed) lattice rule as well as more involved cases where the lattice is a polynomial lattice and the operation becomes polynomial multiplication, or the point set is to be used as an open sequence. For each possible implementation we want to be able to apply specific optimizations and this without having to hand code each case. These goals are pursued in C\texttt{++} in a generic programming style by the use of templates and concepts. In this way it becomes possible to make an abstract mathematical implementation at a high level (being the underlying algebraic structure) and at the same time provide specific optimized implementations where this makes sense. Hence, this presentation shows a case study on how to mix maths and computer science to obtain a usefull (i.e., efficient, reliable, flexible, $\ldots$) software library. Publication status: published KU Leuven publication type: IMa Appears in Collections: NUMA, Numerical Analysis and Applied Mathematics Section