Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points
The obtained results of the paper solve the problem of minimizing the worst-case error of quasi-Monte Carlo integration of the functions in the unit ball of a tensor product reproducing kernel weighted Hilbert space. For an approximation of integrals over the \(s\)-dimensional unit cube it is proposed to use an equal weight cubature rule with a rank-1 lattice point sets. The construction of these rank-1 lattice point sets depends on integer vector, called the generating vector of the lattice. The worst-case error of the integration in this functional space over the proposed rank-1 lattice point sets is written in the terms of the generating vector. The main aim is to choose the generating vector which minimizes the worst-case error of the integration. A special algorithm to find the values of the components of the generating vector is proposed, the so-called component-by-component algorithm. The component-by-component algorithm finds values of the components of the generating vector one component at a time, while keeping the previously made choices fixed. This process starts with the first component of the generating vector and 1-dimensional rule is constructed, then the process continues to find the second component for 2-dimensional rule and so on, and in each step the criterion of choice of the components is to minimize the worst-case error. At first, the above technique was developed by the authors in the case when the number of the points of lattice \(n\) is a prime. In the presented paper this algorithm is generalized for an arbitrary \(n\). The component-by-component algorithm is given in the form of matrix-vector product. This matrix-vector product can be done in time of order \(O(n\log(n))\) and requires memory of order \(O(n)\). It is shown that for any positive integer \(n\) the construction of \(s\)-dimensional rank-1 lattice with \(n\) points has a total construction cost of order \(O(sn\log(n))\) and needs memory of order \(O(n)\). Some illustrative examples are given in three cases for the number \(n\) of the points of lattice: when \(n\) is a prime, a prime powers, and for an arbitrary \(n\).
- Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
- Fast component-by-component construction, a reprise for different kernels
- Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
- Reducing the construction cost of the component-by-component construction of good lattice rules
- Component-by-component construction of good lattice rules with a composite number of points
- Component-by-component construction of good lattice rules
- Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces
- Constructing Randomly Shifted Lattice Rules in Weighted Sobolev Spaces
- Contemporary abstract algebra.
- Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
- Fast component-by-component construction, a reprise for different kernels
- scientific article; zbMATH DE number 3650737 (Why is no real title available?)
- scientific article; zbMATH DE number 1246220 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- scientific article; zbMATH DE number 2051215 (Why is no real title available?)
- On the convergence rate of the component-by-component construction of good lattice rules
- Reducing the construction cost of the component-by-component construction of good lattice rules
- When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
- 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
- Successive coordinate search and component-by-component construction of rank-1 lattice rules
- Component-by-component construction of good lattice rules with a composite number of points
- Random weights, robust lattice rules and the geometry of the \(cbcrc\) algorithm
- Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness
- Hiding the weights -- CBC black box algorithms with a guaranteed error bound
- 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
- Analysis of quasi-Monte Carlo methods for elliptic eigenvalue problems with stochastic coefficients
- Proof techniques in quasi-Monte Carlo theory
- Multi-level quasi-Monte Carlo finite element methods for a class of elliptic PDEs with random coefficients
- Constructing lattice rules based on weighted degree of exactness and worst case error
- Lattice rules for nonperiodic smooth integrands
- Constructions of general polynomial lattice rules based on the weighted star discrepancy
- A note on the CBC-DBD construction of lattice rules with general positive weights
- Component-by-component construction of good lattice rules
- Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond
- Very low truncation dimension for high dimensional integration under modest error demand
- Some results on the complexity of numerical integration
- The construction of good extensible rank-1 lattices
- Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions
- Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
- On combined component-by-component constructions of lattice point sets
- Comparison of Point Sets and Sequences for Quasi-Monte Carlo and for Random Number Generation
- Variance bounds and existence results for randomly shifted lattice rules
- scientific article; zbMATH DE number 2051215 (Why is no real title available?)
- scientific article; zbMATH DE number 2051222 (Why is no real title available?)
- A reduced fast component-by-component construction of lattice points for integration in weighted spaces with fast decreasing weights
- Quasi--Monte Carlo Integration for Affine-Parametric, Elliptic PDEs: Local Supports and Product Weights
- Multilevel QMC with product weights for affine-parametric, elliptic PDEs
- Effective dimension of some weighted pre-Sobolev spaces with dominating mixed partial derivatives
- Reducing the construction cost of the component-by-component construction of good lattice rules
- Quasi-Monte Carlo finite element methods for elliptic PDEs with lognormal random coefficients
- Multilevel quasi-Monte Carlo integration with product weights for elliptic PDEs with lognormal coefficients
- Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients: a survey of analysis and implementation
- Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
- Multilevel Quasi-Monte Carlo Uncertainty Quantification for Advection-Diffusion-Reaction
- Constructing QMC Finite Element Methods for Elliptic PDEs with Random Coefficients by a Reduced CBC Construction
- Rank-1 Lattices and Higher-Order Exponential Splitting for the Time-Dependent Schrödinger Equation
- Fast component-by-component construction of lattice algorithms for multivariate approximation with POD and SPOD weights
- Uncertainty Quantification Using Periodic Random Variables
- Strang splitting in combination with rank-1 and rank-r lattices for the time-dependent Schrödinger equation
- Fast QMC matrix-vector multiplication
- Discrepancy theory and quasi-Monte Carlo integration
- A component-by-component construction for the trigonometric degree
- Fast component-by-component construction, a reprise for different kernels
- Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights
- Random-prime-fixed-vector randomised lattice-based algorithm for high-dimensional integration
- On a reduced component-by-component digit-by-digit construction of lattice point sets
- Weighted compound integration rules with higher order convergence for all N
- Lattice-based integration algorithms: Kronecker sequences and rank-1 lattices
- Comparison of two search criteria for lattice-based kernel approximation
- Constructing embedded lattice-based algorithms for multivariate function approximation with a composite number of points
- The star discrepancy of a union of randomly digitally shifted Korobov polynomial lattice point sets depends polynomially on the dimension
- A component-by-component approach to efficient numerical integration over products of spheres
- The construction of good extensible Korobov rules
- On the convergence rate of the component-by-component construction of good lattice rules
- On a projection-corrected component-by-component construction
- Quasi-Monte Carlo methods with applications in finance
- Randomly shifted lattice rules with the optimal rate of convergence for unbounded integrands
This page was built for publication: Fast component-by-component construction of rank-1 lattice rules with a non-prime number of points
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2489147)
