Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces

DOI10.1090/S0025-5718-06-01785-6zbMath1094.65004WikidataQ57778912 ScholiaQ57778912MaRDI QIDQ3377002

Dirk Nuyens, Ronald Cools

Publication date: 27 March 2006

Published in: Mathematics of Computation (Search for Journal in Brave)

zbMATH Keywords

numerical resultsfast algorithmrank-1 lattice rulesperiodic functionscomponent-by-component algorithmkernel matrix\(s\)-dimensional integrals

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Multidimensional problems (41A63) Approximate quadratures (41A55) Numerical quadrature and cubature formulas (65D32)

Related Items (only showing first 100 items - show all)

Very low truncation dimension for high dimensional integration under modest error demand ⋮ QUASI-MONTE CARLO METHODS FOR HIGH-DIMENSIONAL INTEGRATION: THE STANDARD (WEIGHTED HILBERT SPACE) SETTING AND BEYOND ⋮ Exponential convergence and tractability of multivariate integration for Korobov spaces ⋮ Are quasi-Monte Carlo algorithms efficient for two-stage stochastic programs? ⋮ Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions ⋮ Shifted lattice rules based on a general weighted discrepancy for integrals over Euclidean space ⋮ Random geometries for optimal control PDE problems based on fictitious domain FEMs and cut elements ⋮ Higher-Order Quasi-Monte Carlo for Bayesian Shape Inversion ⋮ Lattice algorithms for multivariate \(L_{\infty}\) approximation in the worst-case setting ⋮ A note on concatenation of quasi-Monte Carlo and plain Monte Carlo rules in high dimensions ⋮ Constructing lattice rules based on weighted degree of exactness and worst case error ⋮ Randomly shifted lattice rules for unbounded integrands ⋮ Design and monitoring of multi‐arm multi‐stage clinical trials ⋮ Construction Schemes for Weighted Lattice Rules ⋮ On combined component-by-component constructions of lattice point sets ⋮ QMC Galerkin Discretization of Parametric Operator Equations ⋮ On the Choice of Weights in a Function Space for Quasi-Monte Carlo Methods for a Class of Generalised Response Models in Statistics ⋮ Component-by-component digit-by-digit construction of good polynomial lattice rules in weighted Walsh spaces ⋮ The construction of good extensible Korobov rules ⋮ Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration ⋮ Construction of interlaced polynomial lattice rules for infinitely differentiable functions ⋮ Construction of good polynomial lattice rules in weighted Walsh spaces by an alternative component-by-component construction ⋮ Construction of interlaced scrambled polynomial lattice rules of arbitrary high order ⋮ Extrapolated Polynomial Lattice Rule Integration in Computational Uncertainty Quantification ⋮ Construction of scrambled polynomial lattice rules over \(\mathbb{F}_{2}\) with small mean square weighted \(\mathcal{L}_{2}\) discrepancy ⋮ Construction-Free Median Quasi-Monte Carlo Rules for Function Spaces with Unspecified Smoothness and General Weights ⋮ On a projection-corrected component-by-component construction ⋮ Some Results on the Complexity of Numerical Integration ⋮ Computational Higher Order Quasi-Monte Carlo Integration ⋮ Numerical Computation of Multivariate Normal Probabilities Using Bivariate Conditioning ⋮ Random weights, robust lattice rules and the geometry of the \(cbcrc\) algorithm ⋮ Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm ⋮ Variance bounds and existence results for randomly shifted lattice rules ⋮ Quasi--Monte Carlo Integration for Affine-Parametric, Elliptic PDEs: Local Supports and Product Weights ⋮ Numerical integration in log-Korobov and log-cosine spaces ⋮ A note on the CBC-DBD construction of lattice rules with general positive weights ⋮ A GPU compatible quasi-Monte Carlo integrator interfaced to pySecDec ⋮ Lattice rules for nonperiodic smooth integrands ⋮ Multilevel QMC with Product Weights for Affine-Parametric, Elliptic PDEs ⋮ Modern Monte Carlo Variants for Uncertainty Quantification in Neutron Transport ⋮ Ian Sloan and Lattice Rules ⋮ The Analysis of Vertex Modified Lattice Rules in a Non-periodic Sobolev Space ⋮ A construction of polynomial lattice rules with small gain coefficients ⋮ QMC integration for lognormal-parametric, elliptic PDEs: local supports and product weights ⋮ Constructing lattice points for numerical integration by a reduced fast successive coordinate search algorithm ⋮ A reduced fast component-by-component construction of lattice points for integration in weighted spaces with fast decreasing weights ⋮ Monte Carlo finite volume element methods for the convection-diffusion equation with a random diffusion coefficient ⋮ Lattice rules in non-periodic subspaces of Sobolev spaces ⋮ Effective Dimension of Some Weighted Pre-Sobolev Spaces with Dominating Mixed Partial Derivatives ⋮ Quasi-Monte Carlo for highly structured generalised response models ⋮ Weighted compound integration rules with higher order convergence for all \(N\) ⋮ Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules ⋮ Lattice rules with random \(n\) achieve nearly the optimal \(\mathcal{O}(n^{-\alpha-1/2})\) error independently of the dimension ⋮ Collider physics at the precision frontier ⋮ Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness ⋮ Quasi-Monte Carlo finite element methods for elliptic PDEs with lognormal random coefficients ⋮ Quasi-Monte Carlo methods for two-stage stochastic mixed-integer programs ⋮ Lattice-Nyström method for Fredholm integral equations of the second kind with convolution type kernels ⋮ Constructions of general polynomial lattice rules based on the weighted star discrepancy ⋮ Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation ⋮ Richardson Extrapolation of Polynomial Lattice Rules ⋮ Periodization strategy may fail in high dimensions ⋮ Lattice-based integration algorithms: Kronecker sequences and rank-1 lattices ⋮ Support points ⋮ Medium-term power planning in electricity markets with pool and bilateral contracts ⋮ Efficient multivariate approximation on the cube ⋮ Hiding the weights -- CBC black box algorithms with a guaranteed error bound ⋮ Intermediate rank lattice rules and applications to finance ⋮ Fast CBC construction of randomly shifted lattice rules achieving \(\mathcal{O}(n^{- 1 + \delta})\) convergence for unbounded integrands over \(\mathbb{R}^s\) in weighted spaces with POD weights ⋮ Constructing good higher order polynomial lattice rules with modulus of reduced degree ⋮ Quasi-Monte Carlo methods with applications in finance ⋮ Randomly shifted lattice rules with the optimal rate of convergence for unbounded integrands ⋮ Lattice rule algorithms for multivariate approximation in the average case setting ⋮ Quasi-Monte Carlo methods for elliptic PDEs with random coefficients and applications ⋮ Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points ⋮ Randomly shifted lattice rules on the unit cube for unbounded integrands in high dimensions ⋮ Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights ⋮ Liberating the dimension ⋮ Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition ⋮ Weighted integration over a hyperrectangle based on digital nets and sequences ⋮ Comparison of Point Sets and Sequences for Quasi-Monte Carlo and for Random Number Generation ⋮ The construction of good extensible rank-1 lattices ⋮ Good low degree rank-1 lattice rules of high dimension ⋮ Computation of the distribution of the maximum of stationary Gaussian processes ⋮ Transformed rank-1 lattices for high-dimensional approximation ⋮ Multilevel quasi-Monte Carlo integration with product weights for elliptic PDEs with lognormal coefficients ⋮ Analysis of quasi-Monte Carlo methods for elliptic eigenvalue problems with stochastic coefficients ⋮ Constrained minimum energy designs ⋮ Higher Order Quasi Monte-Carlo Integration in Uncertainty Quantification ⋮ Multidimensional pseudo-spectral methods on lattice grids ⋮ Lattice algorithms for multivariate approximation in periodic spaces with general weight parameters ⋮ Good lattice rules based on the general weighted star discrepancy ⋮ Automatic evaluations of cross-derivatives ⋮ Model-free global likelihood subsampling for massive data ⋮ Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces ⋮ Proof techniques in quasi-Monte Carlo theory ⋮ Approximation of multivariate periodic functions by trigonometric polynomials based on rank-1 lattice sampling ⋮ Quasi-Monte Carlo methods for linear two-stage stochastic programming problems ⋮ Fast construction of higher order digital nets for numerical integration in weighted Sobolev spaces ⋮ Multi-level quasi-Monte Carlo finite element methods for a class of elliptic PDEs with random coefficients

Uses Software

• FFTW

Cites Work

• Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces
• Liberating the weights
• Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points
• Component-by-component construction of good lattice rules
• Constructing Randomly Shifted Lattice Rules in Weighted Sobolev Spaces
• Reducing the construction cost of the component-by-component construction of good lattice rules
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces