Download PDF

Fast construction of good lattice rules

Publication date: 2007-04

Author:

Nuyens, Dirk

Abstract:

We ontwikkelen een snel algoritme voor de constructie van goede rang-1-roosterregels voor het benaderen van multivariate integralen. Een gekende methode voor de constructie van deze roosterregels is de component-per-component methode. De zo bekomen roosterregels hebben een optimale orde van convergentie. Hun constructiekost is O(s² n²) voor een regel in s dimensies met n punten. We tonen aan hoe we goede rang-1-roosterregels kunnen construeren in tijd O(s n log(n)) en geheugen O(n) met een nieuw algoritme dat we snelle component-per-component constructie noemen. We tonen dit eerst aan in het geval dat n een priemgetal is en de roosterregel wordt opgesteld voor een gewogen, verschuivingsinvariante en tensorproductvorm Hilbertruimte met reproducerende kern. We tonen dit ook aan voor het geval de gewichten orde-afhankelijk zijn en de ruimte hierdoor geen tensorproductvorm meer heeft. Ook indien n geen priemgetal is, blijkt de snelle constructie mogelijk te zijn. De constructie wordt wel moeilijker indien n uit veel verschillende priemfactoren bestaat. Een interessant geval doet zich voor bij machten van een priemgetal. In dat geval kunnen we op een snelle manier roosterrijen construeren die punt per punt gebruikt kunnen worden. Twee natuurlijke uitbreidingen van het component-per-component algoritme zijn de constructie van veeltermroosterregels en de constructie van stempelregels. We tonen aan dat ook in deze gevallen een snelle constructie mogelijk is. De kwaliteit van de roosterregels wordt gedemonstreerd aan de hand van enkele praktijkvoorbeelden.