Information Technology Reference
In-Depth Information
u
i,j
=
∞
u
i,j,
b
−
,
and
u
i
=(
u
i,
1
,...,u
i,s
)
.
(17)
=1
In practical implementations, only the first
r
rows of the
C
j
's are nonzero, for
some positive integer
r
(for example, with
b
r
2
31
on 32-bit computers).
It is usually the case that the first
k
rows of each
C
j
form a nonsingular
k
≈
×
k
matrix, so each one-dimensional projection
P
n
(
{
j
}
) truncated to the first
k
digits
is equal to
Z
n
/n
=
{
0
,
1
/n,...,
(
n
−
1)
/n
}
.Theroleofeach
C
j
is to define a
permutation of
Z
n
/n
so that these numbers are enumerated in a different order
for the different coordinates. The choice of these permutations determines the
uniformity of
P
n
and of its projections
P
n
(
) (which are also digital nets).
In a more general definition of digital net [4], one can also apply bijections (or
permutations) to the digits of
u
Z
b
before and after the multiplication by
C
j
.These
multiplications are performed in an arbitrary ring
R
of cardinality
b
,andthe
bijections may depend on
and
j
. The bijections provide additional opportunity
for improving the uniformity.
A
digital sequence in base
b
is defined by selecting matrices
C
j
with an in-
finite number of columns. This gives an infinite sequence of points. For each
k
, the first
k
columns determine the first
b
k
points, which form a digital net.
Widely-used instances of digital sequences are those of Sobol' [54] in base 2, of
Faure [55] in prime base
b
, of Niederreiter [56], and of Niederreiter and Xing
[57]. With an infinite sequence of matrices
C
j
, we have an infinite-dimensional
digital net. These infinite sequences of columns and matrices are often defined
via recurrences (each column and matrix being a function of the previous ones).
Polynomial lattice rules
use point sets defined by a lattice as in (12), but where
the
h
j
are polynomials over
Z
b
, and the coordinates of the
v
j
are polynomials
over
Z
b
divided by a common polynomial of degree
k
. The output is produced
simply by “evaluating” each
v
(
z
), which is a vector of formal series in
z
,at
z
=
b
. These polynomial lattice rules turn out to be special cases of digital nets
in base
b
. Moreover, much of the theory developed for ordinary lattice rules has
a counterpart for those other types of lattice rules [58,59].
Important parts of this theory also extends to digital nets in general [60,61].
In particular, there is a dual space
C
s
that plays the same role as the dual lattice
L
s
(in the case of polynomial lattice rules,
C
s
is also a lattice). For a digital net
with a random digital shift in base
b
, in analogy with (14), the RQMC estimator
has variance
Var[
μ
n,
rqmc
]=
f
(
h
)
2
,
0
=
h
∈C
s
|
|
(18)
where the
f
(
h
) are the coecients of the Walsh expansion of
f
.Foragiven
f
, this expression provides an ultimate discrepancy measure for a digital net
with a random digital shift. This discrepancy has the same limitations as (14)
for ordinary lattices (the Walsh coecients are usually unknown, etc), and the
practical alternatives are analogous. They lead to figures of merit as in (13), but
where the
(
C
∗
(
u
) are lengths of shortest vectors in the dual spaces
u
)associated
) instead of in the dual lattices
L
∗
(
with the projections
P
n
(
u
u
).
