K-optimal lattice rules

This is an attempt to give a brief overview over the underlying mathematics. As all brief descriptions you will in some places find this description to superficial and in other places incomprehensible. The paper by Ronald Cools and James N. Lyness gives a far better and more in depth introduction to the topic.

Lattice rules

Lattice rules are used for the numerical approximation of multidimensional integrals over the unit hypercube. They are designed for integrating naturally periodic integrands. This assumption is sustained by their error functional, which can be expressed as

$$Ef = If - Qf = \sum_{\forall r \in \Lambda^{\perp}} a_r(\hat{f})$$ (1)

Where a_r(f) are the Fourier coefficients of the integrand and $\Lambda^{\perp}$ is the reciprocal lattice. Since the Fourier coefficients decay rapidly for large $\mid r \mid$ for natural periodic integrands, we seek lattice rules, Q, for which $\Lambda^{\perp}$ has as few points as possible for small $\mid r \mid$.

To attain high degree, d, we seek lattices $\Lambda^{\perp}$with elements as far from the origin as possible. The 1-norm of the point closest to the origin, $\delta$, defines the trigonometric degree, d, as $d = \delta -1$.

A cubature rule need not only be accurate, a good rule is also economical. A convenient measure of the cost of the rule is N(Q), the number of function evaluation needed to carry out the calculation. This depends directly on the density of the points in the lattice $\Lambda^{\perp}$.

An optimal rule of degree, d, is optimal if its abscissas count is less or equal to the abscissa count of any other rule of degree d. Optimal rules are known for all degrees in dimension 1 and 2. For higher dimension optimal rules are only known for the degree 0,1,2 and 3. All these rules are known to be lattice rules, thus it is reasonable to restrict the search for rules of optimal trigonometric degree to lattice rules.

K-optimal lattice rules

Ronald Cools and James Lyness have recently conducted a computer search for good lattice rules in dimension 3 and 4. They define a class of lattices $K(s,\delta)$ and restrict their search to either this class, or well defined subclass of this. There are good reasons to believe that any optimal lattice rule belongs to class $K(s,\delta)$, but this has not been proved. The optimal rule within this class is called K-optimal.

A member of $K(s,\delta)$ is characterized by having generating vectors on s different facets of the s-dim octahedron.

The number of lattice rules in $K(s,\delta)$

In s-dimension there is (s+$\delta$-1 over s-1) points on a facet in distance delta from origin. Taking s generator vectors from s different facets generates M(s,$\delta$)= (s+$\delta$-1 over s-1)^s different lattices. An s-dimensional octahedron has 2^s facets. Taking the generator vector a or -a makes no difference as all points on the lattice is linear combinations of the generator vectors. We can therefor restrict ourself to facet-pair where all vector, a, on facet belongs to the same facet-pair as -a. This leaves us with 2^(s-1) Facet pairs. There is (2^(s-1) over s) ways to pick s vectors from 2 different facet pairs. For s = 5 this number is 4360. One such choice is called a quintet. In a naive approach we would have to check all the M(s,$\delta$) lattices for all the 4360 quintets, to be sure we get the K-optimal lattice. However, a huge saving is possible if we group the quintets in equivalence classes. Any lattice in a particular quintet has a symmetric copy, in all the other quintets of the same equivalence class, and they share fundamental properties such as degree and abscissa count. Thus in searching for K-optimal lattices we only have to inspect one member of each equivalence class. In dimension 5 the 4360 individual quintets are then reduced to 11 equivalence classes.

Our previous search has only covered one equivalence class. Now the program is modified so it might cover all 11. An input parameter decides whether the search should be over all equivalence classes or only the basic equivalence class.

Even when restricted to only one equivalence class, the search become exhaustive for large $\delta$. A further restriction is then applied. By symmetry argument one might hope it is sufficient to consider only a generator vector a at the first facet in which the size of the coordinates are ordered. This will reduce the number of candidate lattices asymptoticly to M(s,$\delta$)/2^s. We name this restriction, searching only the small triangle. It is necessary to point out that the small triangle search misses out on some lattices in the corresponding equivalence class and thus no guaranty the K-optimal rule of the associated equivalence class is found anymore.

Different search modes

Our code for this search is based on the original code developed by Cools and Lyness. We have modified their code so it can do the search in any dimension and parallelized it in a master slave style. The parallelism is very coarse grained. A typical task takes anything from 1 to 10 hours to complete, and the amount of data exchange between the master and a slave is very small. Thus it is well suited for distributed computing over the Internet, and we like to invite you all to be a part of this.

Corresponding to the different savings discussed above we have now modified the code to permit us to set the search space to any of the 3 modes:

1. Full search over all equivalence classes.

2. Full search over the basic equivalence class only.

3. Restricted search over small triangle, only basic equivalence class.

Note that our previous searches have been mode 3 search only, while our current plans are to conduct a full mode 1 search for lower degrees.

Technical details on how the search is carried out can be found here and instruction on how to participate is here.

We've also written a white paper on our previous search available here.