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)
Search WWH ::




Custom Search