publications

2024

1. A unified treatment of tractability for approximation problems defined on Hilbert spaces

   Onyekachi Emenike, Fred J. Hickernell, and Peter Kritzer

   Journal of Complexity, 2024

   Abs

   A large literature specifies conditions under which the information complexity for a sequence of numerical problems defined for dimensions 1,2,… grows at a moderate rate, i.e., the sequence of problems is tractable. Here, we focus on the situation where the space of available information consists of all linear functionals, and the problems are defined as linear operator mappings between Hilbert spaces. We unify the proofs of known tractability results and generalize a number of existing results. These generalizations are expressed as five theorems that provide equivalent conditions for (strong) tractability in terms of sums of functions of the singular values of the solution operators.

2023

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

   Peter Kritzer, and Onyekachi Osisiogu

   Uniform Distribution Theory, 2023

   Abs

   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.

2022

1. Construction of Good Polynomial Lattice Rules in Weighted Walsh Spaces by an Alternative Component-by-Component Construction

   Adrian Ebert, Peter Kritzer, Onyekachi Osisiogu, and Tetiana Stepaniuk

   Mathematics and Computers in Simulation, 2022

   Abs

   We study the efficient construction of good polynomial lattice rules, which are special instances of quasi-Monte Carlo (QMC) methods. The integration rules obtained are of particular interest for the approximation of multivariate integrals in weighted Walsh spaces. In particular, we study a construction algorithm which assembles the components of the generating vector, which is in this case a vector of polynomials over a finite field, of the polynomial lattice rule in a component-wise fashion. We show that the constructed QMC rules achieve the almost optimal error convergence order in the function spaces under consideration and prove that the obtained error bounds can, under certain conditions on the involved weights, be made independent of the dimension. We also demonstrate that our alternative component-by-component construction, which is independent of the underlying smoothness of the function space, can be implemented relatively easily in a fast manner. Numerical experiments confirm our theoretical findings.

2. Component-by-Component Digit-by-Digit Construction of Good Polynomial Lattice Rules in Weighted Walsh Spaces

   Adrian Ebert, Peter Kritzer, Onyekachi Osisiogu, and Tetiana Stepaniuk

   Constructive Approximation, 2022

   Abs

   We consider the efficient construction of polynomial lattice rules, which are special cases of so-called quasi-Monte Carlo (QMC) rules. These are of particular interest for the approximate computation of multivariate integrals where the dimension d may be in the hundreds or thousands. We study a construction method that assembles the generating vector, which is in this case a vector of polynomials over a finite field, of the polynomial lattice rule in a digit-by-digit (or, equivalently, coefficient-by-coefficient) fashion. As we will show, the integration error of the corresponding QMC rules achieves excellent convergence order, and, under suitable conditions, we can vanquish the curse of dimensionality by considering function spaces equipped with coordinate weights. The construction algorithm is based on a quality measure that is independent of the underlying smoothness of the function space and can be implemented in a fast manner (without the use of fast Fourier transformations). Furthermore, we illustrate our findings with extensive numerical results.

2021

1. Digit-by-Digit and Component-by-Component Constructions of Lattice Rules for Periodic Functions with Unknown Smoothness

   Adrian Ebert, Peter Kritzer, Dirk Nuyens, and Onyekachi Osisiogu

   Journal of Complexity, 2021

   HTML