A Kronecker Product Construction for Digital Nets
An analogy of (t,m, s)-nets with codes, viz. the notion of the dual space of a digital net, is used to obtain a new way of constructing digital nets. The method is reminiscent of the Kronecker product code construction in the theory of linear codes.
- PDF / 1,126,549 Bytes
- 10 Pages / 439.37 x 666.14 pts Page_size
- 53 Downloads / 192 Views
2
Depar tment of Mathemati cs, National University of Singapore, 2 Science Driv e 2, Singapore 117543, Republic of Sing ap ore E-m ail: nied~math . nus. edu . sg Institute of Dis cret e Mathem atics, Austrian Acad emy of Sciences , Sonnenfelsgasse 19, A-lOlO Vienn a , Aus tria E-m ail: gottlieb .pirsic~oeaY.ac.at
Abstract. An anal ogy of (t , m , s)-n ets with codes, viz. t he notion of the du al space of a digit al net , is used to obtain a new way of construct ing digital nets . The method is reminiscent of the Kronecker product code const ruct ion in the theory of linear codes.
1
Introduction
In the theory of low-discrepancy point set s, digit al (t , m, s)-nets ar e an import ant class of point sets . Their distribution properties in terms of bounds on the star discrepan cy ar e currently among the best, hence their relevan ce for quasi-Monte Carlo methods. (See [7, Chapter 4]' [8], [11, Chap ter 8] for further background on (t ,m, s)-nets.) Whil e t he connect ion with the notion of discrepan cy puts (t, m , s)-nets properly in the fields of analysis and numb er th eory, th ere are also close links to combinatorial structures such as linear codes or generalized orthogonal arrays. There ar e alr eady a number of pap ers that use the analogies to linear codes, for instance [1], [2]' [3], [10], [12]' [13] (see also [10, Section 6] for some mor e references) . In this pap er it is th e notion of duality of linear codes applied to digit al nets, as pr esent ed by th e authors in [9] (note also a related approach in [14]) , that is employed to give a new construction of digit al nets .
2
Definitions
We begin with th e definition of a digit al (t , m , s)-n et. In this pap er this is done in a way t hat emphasizes the ana logy with linear codes, as these are defined simply as linear subspaces of 1Fb . We use t he st andard not ation lFb for the finit e field of order b. Not e that in the following, point sets are understood as multisets, i.e., with multipliciti es assign ed t o their elements. K.‒T. Fang et al. (eds.)., Monte Carlo and Quasi-Monte Carlo Methods 2000 © Springer-Verlag Berlin Heidelberg 2002
397
D efi n ition 1. Let b ~ 2 , s ~ 1,t , m be int egers with 0:S t:S m . A (t, m ,s)net in base b is a poin t (multi-)set of b'" points in [0, l )" such t hat t he number of points in each interval s
I1 [aib- di , (ai + l )b- di ) ~ [O, l)S ,
ai, di E Z::::o,
i=l
with 2:: : = 1 d i = m - t is bt . (T his is exactly t he number of points expected und er equidist ribut ion.) D efin it io n 2. Let b be a prime power. A digital (t , m , s) -net construc ted over IFb is a (t, m , s)-net t hat is t he image of a linear subspace of (IFb)S, m ~ 1, of dim ension k :S m und er t he map ((a1,1 , .. . , a1,m),. ' " (a s,l , .. . , as,m)) E (IFb)S 1-+
(2:::
1
a1,ib- i , ... ,
2:::
1
as,ib-i) E [0, n-,
(1)
where aj,i 1-+ aj,i are fixed bijections from IFb t o {O, . . . , b - I} C Z for each i, j . The points ar e assigned t he multiplicity bm - k . We recall the upp er discrepan cy bound for (t, m, s) -n
Data Loading...
