Information Technology Reference
In-Depth Information
which can be computed in
O
(
ns
) time. This discrepancy is a weighted version
of a criterion known as
P
2
α
[11,20], widely used for lattice rules.
It is known that for any given dimension
s
and arbitrarily small
δ>
0, there
exist lattice rules whose discrepancy (15) is
O
(
n
−α
+
δ
) [47,4,20]. Until very re-
cently, it was unclear if those lattices were easy to find, but explicit construction
methods are now available.
Indeed, for a large
s
and moderate
n
, trying all possibilities for the basis
vectors is just impractical. Even if we restrict ourselves to a rank-1 lattice, there
is already (
n
1)
s
possibilities. So one must either search at random, or perform
a more restricted search. One possibility is to limit the search to Korobov rules,
so that there is only the parameter
a
1
to select. Another possibility is to adopt
a greedy component-by-component (CBC) construction of a rank-1 lattice, for a
given
n
, by selecting the components
a
j
of the vector
a
1
=(
a
1
,...,a
s
) iteratively
as follows [48,49]. Start with
a
1
=1.Atstep
j
,
a
1
,...,a
j−
1
are fixed and we
select
a
j
to optimize a given discrepancy measure for the
j
-dimensional rank-1
lattice with generating vector
v
1
=
a
1
/n
. At each step, there is at most
n
−
1
choices to examine for
a
j
,soatmost
O
(
ns
) discrepancies need to be computed
to construct a lattice of dimension
s
. For a discrepancy of the form (15), since
each discrepancy is computable in
O
(
ns
) time, we can conclude that computing
a
1
=(
a
1
,...,a
s
)requiresatmost
O
(
n
2
s
2
) time. But in fact, faster algorithms
have been designed that can compute
a
1
in
O
(
n
log(
n
)
s
)timeusing
O
(
n
)memory
[50,48,51].
The remarkable feature of these CBC constructions is that for a large variety
of discrepancies, defined mostly via RKHS, it has been proved that one obtains
rank-1 lattices whose discrepancy converges at the same rate, as a function of
n
, as the best possible lattice constructions [50,52,47,53]. In other words, for
these discrepancies, CBC provides a practical way of constructing lattices with
optimal convergence rate of the discrepancy. These results provide supporting
arguments for the use of these types of discrepancies as figures of merit.
−
6 Digital Nets for QMC
We start with an arbitrary integer
b
≥
2, usually a prime. An
s
-dimensional
digital net in base
b
,with
n
=
b
k
{
u
0
,...,
u
n−
1
}
defined by selecting
s
generator matrices
C
1
,...,
C
s
with elements in
points, is a point set
P
n
=
Z
b
=
{
0
,...,b
−
1
}
,whereeach
C
j
is
∞×
k
.Thepoints
u
i
are defined as follows. For
i
=0
,...,b
k
−
1, we write
k−
1
a
i,
b
,
i
=
=0
⎛
⎝
⎞
⎠
⎛
⎝
⎞
⎠
a
i,
0
a
i,
1
.
a
i,k−
1
u
i,j,
1
u
i,j,
2
.
=
C
j
mod
b,
(16)