Nuyens, Dirk ;
Cools, Ronald
Fast ComponentByComponent Construction of Rank1 Lattice Rules for (Non)Primes (Part II)
Abstract
Part I: (this part of the talk by Ronald Cools)
We restate our previous result which showed that it is possible to
construct the generating vector of a rank1 lattice rule in a fast way,
i.e. O(s n log(n)), with s the number of dimensions and n the number of
points assumed to be prime. Here we explicitly use basic facts from
algebra to exploit the structure of a matrix  which introduces the
crucial cost in the construction  to get a matrixvector
multiplication in time O(n log(n)) instead of O(n^2). We again stress
the fact that the algorithm works for any tensor product reproducing
kernel Hilbert space.
Part II: (this part of the talk by Dirk Nuyens)
In the second part we generalize the tricks used for primes to
nonprimes, by basically falling back to algebraic group theory. In
this way it can be shown that also for a nonprime number of points,
this crucial matrixvector multiplication can be done in time O(n
log(n)). We conclude that the construction of rank1 lattice rules in
an arbitrary r.k.h.s. for an arbitrary amount of points can be done in a
fast way of O(s n log(n)).
BibTeX  Entry
@InProceedings{nuyens_et_al:DSP:2005:148,
author = {Dirk Nuyens and Ronald Cools},
title = {Fast ComponentByComponent Construction of Rank1 Lattice Rules for (Non)Primes (Part II)},
booktitle = {Algorithms and Complexity for Continuous Problems},
year = {2005},
editor = {Thomas M{\"u}llerGronbach and Erich Novak and Knut Petras and Joseph F. Traub},
number = {04401},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2005/148},
annote = {Keywords: numerical integration , cubature/quadrature , rank1 lattice , componentbycomponent construction , fast algorithm}
}
Keywords: 

numerical integration , cubature/quadrature , rank1 lattice , componentbycomponent construction , fast algorithm 
Seminar: 

04401  Algorithms and Complexity for Continuous Problems

Issue date: 

2005 
Date of publication: 

19.04.2005 