Reduced digital nets
V. Anupindi, P. Kritzer · 2025
Read Reduced digital nets by V. Anupindi, P. Kritzer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-13659.txt.
Introduction
Vishnupriya Anupindi and Peter Kritzer study reduced digital nets, point sets used in fast numeric integration. Their paper from twenty twenty-five builds on recent work where trimmed nets speed up matrix-vector products. Quasi-Monte Carlo rules use such point sets as sample nodes. Trimming rows or columns of the net's matrices cuts the cost.
The authors bound the quality score of row-reduced and column-row-reduced nets. These bounds feed the error study of rules built on the trimmed sets. They also compare the three trims: row, column, and both at once. Notes on further angles round out the piece. The results help users know what accuracy they trade for speed. The work serves fields where such products recur, from finance to physics sims.
Catalog record
| CREATOR | V. Anupindi, P. Kritzer |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-13659
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reduced digital nets V. Anupindi, P. Kritzer Abstract In the recent papers “The fast reduced QMC matrix-vector product” (J. Comput. Appl. Math. 440, 115642, 2024) and “Column reduced digital nets” (submitted), it was proposed to use QMC rules based on reduced digital nets which provide a speed-up in the computation of QMC vector-matrix products that may occur in practical applications. In this paper, we provide upper bounds on the quality parameter of row reduced and column-row reduced digital nets, which are helpful for the error analysis of using reduced point sets as integration nodes in a QMC rule. We also give remarks on further aspects and comparisons of row reduced, column reduced, and column-row reduced digital net. 1 Introduction 1.1 The problem setting In various fields like statistics, finance, and uncertainty quantification, one needs to numerically compute integrals of the form \int_{D}f({\bm{x}}^{\top}A){\mathrm{d}}\mu({\bm{x}}), (1) where A is a real s\times\tau matrix, D\subseteq{\mathbb{R}}^{s} , and \mu is a suitable measure, by quasi-Monte Carlo (QMC) rules, Q_{N}(f):=\frac{1}{N}\,\sum_{k=0}^{N-1}f({\bm{x}}_{k}^{\top}A). (2) Here, the {\bm{x}}_{k}=(x_{k}^{(1)},\ldots,x_{k}^{(s)})^{\top} , k\in\{0,1,\ldots,N-1\} , are column vectors corresponding to the points used in the QMC rule. For the sake of simplicity, we assume that D=[0,1]^{s} , and choose \mu as the Lebesgue measure in the following. We are interested in the cases where the vector-matrix product {\bm{x}}_{k}^{\top}A is a significant factor in the computation of ( 2 ). In special circumstances, one can modify A such that it allows a fast vector-matrix multiplication, see [ 6 , 8 ] . However, in this paper, we do not modify the matrix A , but we focus on obtaining special quadrature points {\bm{x}}_{0},\dots,{\bm{x}}_{N-1} that speed-up the computation of the vector-matrix product {\bm{x}}_{k}^{\top}A for k\in\{0,1,\ldots,N-1\} . We define the N\times s -matrix X=\begin{pmatrix}{\bm{x}}_{0}^{\top}\\ \vdots\\ {\bm{x}}_{N-1}^{\top}\\ \end{pmatrix}, (3) i.e., the k -th row is the k -th point {\bm{x}}_{k} of the quadrature rule. Computing the vector-matrix products {\bm{x}}_{k}^{\top}A for k\in\{0,1,\ldots,N-1\} is equivalent to computing the matrix-matrix product XA , which requires {\mathcal{O}}(N\,s\,\tau) operations. In [ 4 ] , the authors showed that by using QMC point sets that are derived from (polynomial) lattice rules or Korobov’s p -sets, one can obtain a speed-up in the matrix-matrix multiplication XA by reordering X to be of circulant structure and using the fast Fourier transformation (FFT). In this case, the cost of evaluating Q_{N}(f) in ( 2 ) can be reduced to {\mathcal{O}}(\tau\,N\,\log N) operations provided that \log N\ll s . In this paper, we take a different route and focus on quadrature points obtained from reduced digital nets. Digital nets, as we know, are efficient and among the most commonly used QMC node sets. To obtain reduced digital nets, we set a certain number of rows, columns, or both rows and columns of the generating matrices C_{j}^{(m)} to zero. The main motivation for doing this is to obtain a certain repetitive structure in the components of the points {\bm{x}}_{k} which can be used to obtain fast computation of the products {\bm{x}}_{k}^{\top}A . The idea of using reduced digital nets was proposed in [ 2 ] , where the authors looked at row reduced digital nets, that is, digital nets where one sets certain rows of the generating matrices to zero. In [ 1 ] , we extended the study to column reduced digital nets. While studying such reduced digital nets, we have four main aspects to consider. The first two pertain to the theoretical aspects, particularly the quality parameter (the so-called t -value) of the reduced net and the error estimate for using reduced nets in quadrature rules. The practical aspects include a fast algorithm for computing the matrix-matrix product using points from a reduced net and implementing the algorithm to obtain some numerical results on the computation time. In [ 2 ] , the authors provided a fast matrix-matrix product algorithm using row reduced digital nets and also provided error estimates assuming that the t -value of the row reduced digital net is known. However, an estimate for the t -value of the row reduced digital net was still missing in [ 2 ] . In [ 1 ] , the authors of the present paper focused on column reduced digital nets, where we gave an estimate for the t -value, an error estimate using this bound, and also provided an algorithm for matrix-matrix multiplication using column reduced digital nets. Furthermore, with numerical experiments, we compared the computation time of row reduced with column reduced digital nets and the standard matrix-matrix multiplication. In this paper, we will revisit the row reduced digital nets as proposed in [ 2 ] . We estimate the quality parameter of these nets and provide an error bound using our result in Corollary 1 below. For an algorithm to compute the matrix-matrix product using row reduced digital nets, we refer to [ 2 , Algorithm 4] . We also comment on a combination of column and row reduced digital nets. In the following, we use {\mathbb{N}} to denote the set of natural numbers starting from 1 and {\mathbb{N}}_{0} to denote the set of whole numbers, which are all the non-negative integers, i.e., {\mathbb{N}}_{0}=\{0,1,2,\dots\} . 1.2 Digital nets and sequences In this section, we recall the definitions and establish notation for digital nets and sequences. Given a prime b , let {\mathbb{F}}_{b} be a finite field with b elements, where the elements of {\mathbb{F}}_{b} can be identified with the set \{0,1,\dots,b-1\} . An elementary interval in base b and dimension s is a half-open interval of the form \prod_{j=1}^{s}[a_{j}b^{-d_{j}},(a_{j}+1)b^{-d_{j}}) , where the a_{j},d_{j} are non-negative integers with 0\leq a_{j}<b^{d_{j}} for 1\leq j\leq s . Definition 1 . For a given dimension s\geq 1 and non-negative integers t,m with 0\leq t\leq m , a (t,m,s) -net in base b is a point set \mathcal{P}\subset[0,1)^{s} consisting of b^{m} points such that any elementary interval in base b with volume b^{t-m} contains exactly b^{t} points of \mathcal{P} . A sequence ({\bm{x}}_{0},{\bm{x}}_{1},\dots) of points in [0,1)^{s} is called a (t,s) -sequence in base b if, for all integers m\geq t and k\geq 0 , the point set consisting of the points {\bm{x}}_{kb^{m}},\dots,{\bm{x}}_{kb^{m}+b^{m}-1} forms a (t,m,s) -net in base b . For a (t,m,s) -net or a (t,s) -sequence, the parameter t , also known as the quality parameter of a net or sequence, is crucial since it is an indicator of how uniformly distributed the points are. In particular, a low t -value is desirable since it implies better equidistribution properties. A (t,m,s) -net is called strict , if it does not fulfill the requirements of a (t-1,m,s) -net (for t\geq 1 ), and analogously for (t,s) -sequences. In general, any (t,m,s) -net is also a (t+1,m,s) -net for t<m . To construct concrete examples of good nets in arbitrary dimension, one frequently uses the digital method introduced by Niederreiter in [ 9 ] . Definition 2 . A digital (t,m,s) -net over {\mathbb{F}}_{b} is a (t,m,s) -net \mathcal{P}=\{{\bm{x}}_{0},\dots,{\bm{x}}_{b^{m}-1}\} where the points are constructed as follows. Let C_{1}^{(m)},\dots,C_{s}^{(m)} in {\mathbb{F}}_{b}^{m\times m} be matrices over {\mathbb{F}}_{b} . To generate the k -th point, 0\leq k\leq b^{m}-1 , in \mathcal{P} , we use the b -adic expansion k=\sum_{i=0}^{m-1}k_{i}b^{i} with digits k_{i}\in\{0,\dots,b-1\} which we denote by \overrightarrow{k}=(k_{0},\dots,k_{m-1})^{\top} . The j -th