<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>In this paper, we study an efficient algorithm for constructing point sets underlying quasi-Monte Carlo integration rules for weighted Korobov classes. The algorithm presented is a reduced fast component-by-component digit-by-digit (CBC-DBD) algorithm, which is useful for situations where the weights in the function space show a sufficiently fast decay. The advantage of the algorithm presented here is that the computational effort can be independent of the dimension of the integration problem to be treated if suitable assumptions on the integrand are met. By considering a reduced digit-by-digit construction, we allow an integration algorithm to be less precise with respect to the number of bits in those components of the problem that are considered less important. The new reduced CBC-DBD algorithm is designed to work for the construction of lattice point sets, and the corresponding integration rules (so-called lattice rules) can be used to treat functions in different kinds of function spaces. We show that the integration rules constructed by our algorithm satisfy error bounds of almost optimal convergence order. Furthermore, we give details on an efficient implementation such that we obtain a considerable speed-up of a previously known CBC-DBD algorithm that has been studied in the paper <italic>Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness</italic> by Ebert, Kritzer, Nuyens, and Osisiogu, published in the Journal of Complexity in 2021. This improvement is illustrated by numerical results.</p>
</abstract>

In this paper, we study an efficient algorithm for constructing point sets underlying quasi-Monte Carlo integration rules for weighted Korobov classes. The algorithm presented is a reduced fast component-by-component digit-by-digit (CBC-DBD) algorithm, which is useful for situations where the weights in the function space show a sufficiently fast decay. The advantage of the algorithm presented here is that the computational effort can be independent of the dimension of the integration problem to be treated if suitable assumptions on the integrand are met. By considering a reduced digit-by-digit construction, we allow an integration algorithm to be less precise with respect to the number of bits in those components of the problem that are considered less important. The new reduced CBC-DBD algorithm is designed to work for the construction of lattice point sets, and the corresponding integration rules (so-called lattice rules) can be used to treat functions in different kinds of function spaces. We show that the integration rules constructed by our algorithm satisfy error bounds of almost optimal convergence order. Furthermore, we give details on an efficient implementation such that we obtain a considerable speed-up of a previously known CBC-DBD algorithm that has been studied in the paper Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness by Ebert, Kritzer, Nuyens, and Osisiogu, published in the Journal of Complexity in 2021. This improvement is illustrated by numerical results.

On a Reduced Component-by-Component Digit-by-Digit Construction of Lattice Point Sets

Uniform distribution theory

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

In this paper, we study an efficient algorithm for constructing point sets underlying quasi-Monte Carlo integration rules for weighted Korobov classes. The...

On a Reduced Component-by-Component Digit-by-Digit Construction of Lattice Point Sets

Published Online: Aug 10, 2023

Page range: 97 - 140

Received: Nov 22, 2022

Accepted: May 11, 2023

DOI: https://doi.org/10.2478/udt-2023-0007

Keywords
Numerical integration, lattice points, quasi-Monte Carlo methods, component-by-component construction, digit-by-digit construction, weighted function spaces, fast implementation

© 2023 Peter Kritzer et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

On a Reduced Component-by-Component Digit-by-Digit Construction of Lattice Point Sets

Published Online: Aug 10, 2023

Page range: 97 - 140

Received: Nov 22, 2022

Accepted: May 11, 2023

DOI: https://doi.org/10.2478/udt-2023-0007

KeywordsNumerical integration, lattice points, quasi-Monte Carlo methods, component-by-component construction, digit-by-digit construction, weighted function spaces, fast implementation

© 2023 Peter Kritzer et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Keywords
Numerical integration, lattice points, quasi-Monte Carlo methods, component-by-component construction, digit-by-digit construction, weighted function spaces, fast implementation