< Terug naar vorige pagina

Publicatie

Fast component-by-component construction of lattice algorithms for multivariate approximation with POD and SPOD weights

Tijdschriftbijdrage - Tijdschriftartikel

In a recent paper by the same authors, we provided a theoretical foundation for the component-by-component (CBC) construction of lattice algorithms for multivariate $ L_2$ approximation in the worst case setting, for functions in a periodic space with general weight parameters. The construction led to an error bound that achieves the best possible rate of convergence for lattice algorithms. Previously available literature covered only weights of a simple form commonly known as product weights. In this paper we address the computational aspect of the construction. We develop fast CBC construction of lattice algorithms for special forms of weight parameters, including the so-called POD weights and SPOD weights which arise from PDE applications, making the lattice algorithms truly applicable in practice. With $ d$ denoting the dimension and $ n$ the number of lattice points, we show that the construction cost is $ \mathcal {O}(d\,n\log (n) + d^2\log (d)\,n)$ for POD weights, and $ \mathcal {O}(d\,n\log (n) + d^3\sigma ^2\,n)$ for SPOD weights of degree $ \sigma \ge 2$. The resulting lattice generating vectors can be used in other lattice-based approximation algorithms, including kernel methods or splines.
Tijdschrift: Mathematics of Computation
ISSN: 0025-5718
Issue: 328
Volume: 90
Pagina's: 787 - 812
Jaar van publicatie:2021
BOF-keylabel:ja
IOF-keylabel:ja
BOF-publication weight:1
CSS-citation score:1
Auteurs:International
Authors from:Higher Education
Toegankelijkheid:Open