Constructions of low-discrepancy point sets and sequences.
Low-discrepancy point sets and sequences play an important role in quasi-Monte Carlo method for numerical integration. They provide good quadrature points for estimating the de nite integrals of functions that cannot be integrated analytically. We study two types of low-discrepancy point se...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/52664 |
| _version_ | 1811695131787526144 |
|---|---|
| author | Yeo, Anderson Siang Jing. |
| author2 | Xing Chaoping |
| author_facet | Xing Chaoping Yeo, Anderson Siang Jing. |
| author_sort | Yeo, Anderson Siang Jing. |
| collection | NTU |
| description | Low-discrepancy point sets and sequences play an important role in quasi-Monte Carlo
method for numerical integration. They provide good quadrature points for estimating
the de nite integrals of functions that cannot be integrated analytically.
We study two types of low-discrepancy point sets and sequences. The rst type is
Halton sequences, introduced by Halton [8]. Halton sequences are explicitly generated
low-discrepancy sequences, where the construction of the terms in Halton sequences
is straightforward through the use of the radical inverse function. The second type
of low-discrepancy point sets and sequences are (t; m; s)-nets and (t; s)-sequences,
introduced by Niederreiter [24]. Both (t; m; s)-nets and (t; s)-sequences are de ned by
means of predetermined distribution property of their terms with respect to a class of
intervals. General principles for the construction of (t; m; s)-nets and (t; s)-sequences
are based on the digital method introduced in [24, Section 6]. This method links
the construction of (t; m; s)-nets to the construction of some Fb-linear subspaces of
Fms
b via duality theory established by Niederreiter and Pirsic [31]. In this thesis, we
present four constructions of low-discrepancy point sets and sequences. The following
is a brief overview of each construction:
The rst construction comes from the direct application of duality theory inspired
by the (a+x; b+x; a+b+x)-construction of linear codes, also known as the tripleerror-
correcting codes. This construction of digital nets is also called the (a + x; b +
x; a + b + x)-construction. This is considered a new construction because it is not a special case of the matrix product construction for digital nets [29] (where the
(u; u + v)-construction [2] is a special case).
The second construction is a generalization of Halton sequence called the doublyin
nite Halton sequence. Many generalizations of Halton sequence that have been
proposed, permute the b-adic digits in the b-adic expansion of the index of Halton
sequence. Our generalization proceeds in a di erent direction. Instead we expand the
index of Halton sequence from the set of non-negative integers to the set of all integers.
The construction of the terms of this sequence uses the Monna map, a generalization
of the radical inverse function to the set of all integers. The star discrepancy of
doubly-in nite Halton sequence can be shown to have the same order of magnitude
as the star discrepancy of classical Halton sequence. Moreover, doubly-in nite Halton
sequence turns out to be symmetric sequence resulting from the symmetrization of
Halton sequence. Symmetric sequence and symmetrization of sequence into symmetric
sequence has been studied in relation to L2-discrepancy [40, 41]. Thus doubly-in nite
Halton sequence being symmetric sequence gives a result on star discrepancy for
symmetric sequence.
The third construction is a new Halton-type sequence from global function elds.
This construction can be viewed as a generalization of Halton sequence, where the
index of the sequence is now taken from elements in a function eld. The generating
algorithm of the terms in this sequence is very similar to the generating algorithm
of terms in the classical Halton sequence. We use a modi ed radical inverse function
for the ring of integers. It turns out that our Halton-type sequence can be t into
the framework of (t; s)-sequences as well, which leads to a better star discrepancy
bound. This gives an explicit and direct formula for the construction of the terms of
(t; s)-sequences, an advantage that is not presented in the digital method for (t; s)-
sequences. To our knowledge, this is also the rst general construction for (t; s)-
sequences that is not directly based on the digital method.
The fourth construction is a digital net derived from algebraic number elds. Thisconstruction utilizes the digital method. However the rows of generating matrices of
this digital net are constructed from the residue eld with respect to a prime ideal
of a number eld. The rows of these generating matrices depend on the choice of
uniformizing parameters from a set of prime ideals which are pairwise coprime and
each of these prime ideals are coprime to the prime ideal used to obtain the residue
eld. Despite not o ering an improvement to the parameters of digital nets, this
construction is rather interesting from the pure mathematics point of view. |
| first_indexed | 2024-10-01T07:18:36Z |
| format | Thesis |
| id | ntu-10356/52664 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T07:18:36Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/526642023-02-28T23:53:41Z Constructions of low-discrepancy point sets and sequences. Yeo, Anderson Siang Jing. Xing Chaoping School of Physical and Mathematical Sciences DRNTU::Science::Mathematics Low-discrepancy point sets and sequences play an important role in quasi-Monte Carlo method for numerical integration. They provide good quadrature points for estimating the de nite integrals of functions that cannot be integrated analytically. We study two types of low-discrepancy point sets and sequences. The rst type is Halton sequences, introduced by Halton [8]. Halton sequences are explicitly generated low-discrepancy sequences, where the construction of the terms in Halton sequences is straightforward through the use of the radical inverse function. The second type of low-discrepancy point sets and sequences are (t; m; s)-nets and (t; s)-sequences, introduced by Niederreiter [24]. Both (t; m; s)-nets and (t; s)-sequences are de ned by means of predetermined distribution property of their terms with respect to a class of intervals. General principles for the construction of (t; m; s)-nets and (t; s)-sequences are based on the digital method introduced in [24, Section 6]. This method links the construction of (t; m; s)-nets to the construction of some Fb-linear subspaces of Fms b via duality theory established by Niederreiter and Pirsic [31]. In this thesis, we present four constructions of low-discrepancy point sets and sequences. The following is a brief overview of each construction: The rst construction comes from the direct application of duality theory inspired by the (a+x; b+x; a+b+x)-construction of linear codes, also known as the tripleerror- correcting codes. This construction of digital nets is also called the (a + x; b + x; a + b + x)-construction. This is considered a new construction because it is not a special case of the matrix product construction for digital nets [29] (where the (u; u + v)-construction [2] is a special case). The second construction is a generalization of Halton sequence called the doublyin nite Halton sequence. Many generalizations of Halton sequence that have been proposed, permute the b-adic digits in the b-adic expansion of the index of Halton sequence. Our generalization proceeds in a di erent direction. Instead we expand the index of Halton sequence from the set of non-negative integers to the set of all integers. The construction of the terms of this sequence uses the Monna map, a generalization of the radical inverse function to the set of all integers. The star discrepancy of doubly-in nite Halton sequence can be shown to have the same order of magnitude as the star discrepancy of classical Halton sequence. Moreover, doubly-in nite Halton sequence turns out to be symmetric sequence resulting from the symmetrization of Halton sequence. Symmetric sequence and symmetrization of sequence into symmetric sequence has been studied in relation to L2-discrepancy [40, 41]. Thus doubly-in nite Halton sequence being symmetric sequence gives a result on star discrepancy for symmetric sequence. The third construction is a new Halton-type sequence from global function elds. This construction can be viewed as a generalization of Halton sequence, where the index of the sequence is now taken from elements in a function eld. The generating algorithm of the terms in this sequence is very similar to the generating algorithm of terms in the classical Halton sequence. We use a modi ed radical inverse function for the ring of integers. It turns out that our Halton-type sequence can be t into the framework of (t; s)-sequences as well, which leads to a better star discrepancy bound. This gives an explicit and direct formula for the construction of the terms of (t; s)-sequences, an advantage that is not presented in the digital method for (t; s)- sequences. To our knowledge, this is also the rst general construction for (t; s)- sequences that is not directly based on the digital method. The fourth construction is a digital net derived from algebraic number elds. Thisconstruction utilizes the digital method. However the rows of generating matrices of this digital net are constructed from the residue eld with respect to a prime ideal of a number eld. The rows of these generating matrices depend on the choice of uniformizing parameters from a set of prime ideals which are pairwise coprime and each of these prime ideals are coprime to the prime ideal used to obtain the residue eld. Despite not o ering an improvement to the parameters of digital nets, this construction is rather interesting from the pure mathematics point of view. Doctor of Philosophy (SPMS) 2013-05-22T02:11:25Z 2013-05-22T02:11:25Z 2013 2013 Thesis http://hdl.handle.net/10356/52664 en 122 p. application/pdf |
| spellingShingle | DRNTU::Science::Mathematics Yeo, Anderson Siang Jing. Constructions of low-discrepancy point sets and sequences. |
| title | Constructions of low-discrepancy point sets and sequences. |
| title_full | Constructions of low-discrepancy point sets and sequences. |
| title_fullStr | Constructions of low-discrepancy point sets and sequences. |
| title_full_unstemmed | Constructions of low-discrepancy point sets and sequences. |
| title_short | Constructions of low-discrepancy point sets and sequences. |
| title_sort | constructions of low discrepancy point sets and sequences |
| topic | DRNTU::Science::Mathematics |
| url | http://hdl.handle.net/10356/52664 |
| work_keys_str_mv | AT yeoandersonsiangjing constructionsoflowdiscrepancypointsetsandsequences |