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.