共查询到20条相似文献,搜索用时 31 毫秒
1.
K. Mark Lawrence 《组合设计杂志》1996,4(4):275-293
We consider (t,m,s)-nets in base b, which were introduced by Niederreiter in 1987. These nets are highly uniform point distributions in s-dimensional unit cubes and have applications in the theory of numerical integration and pseudorandom number generation. A central question in their study is the determination of the parameter values for which these nets exist. Niederreiter has given several methods for their construction, all of which are based on a general construction principle from his 1987 paper. We define a new family of combinatorial objects, the so-called “generalized orthogonal arrays,” and then discuss a combinatorial characterization of (t.m.s)-nets in base b in terms of these generalized orthogonal arrays. Using this characterization, we describe a new method for constructing (t.m.s)-nets in base b that is not based on the aforementioned construction principle. This method gives rise to some very general conditions on the parameters (involving a link with the theory of orthogonal arrays) that are sufficient to ensure the existence of a (t.m.s)-net in base b. In this way we construct many nets that are new. © 1996 John Wiley & Sons, Inc. 相似文献
2.
In quasi-Monte Carlo methods, point sets of low discrepancy are crucial for accurate results. A class of point sets with low theoretic upper bounds of discrepancy are the digital point sets known as digital (t, m, s)-nets which can be implemented very efficiently. The parameter t is indicative of the quality; i.e., small values of t lead to small upper bounds of the discrepancy. We introduce an effective way to establish this quality parameter t for digital nets constructed over arbitrary finite fields and give an application to the construction of digital nets of high quality. 相似文献
3.
《Mathematical and Computer Modelling》1996,23(8-9):1-8
It is well known that (t, m, s)-nets are useful in numerical analysis. Many of the constructions of such nets arise from number theoretic or algebraic constructions. Less well known is the fact that combinatorial constructions also yield nets with very good and in many cases, optimal parameters. In this paper, we provide a survey of such combinatorial constructions of (t, m, s)-nets. 相似文献
4.
Art B. Owen 《Journal of Complexity》1998,14(4):466-489
Hybrids of equidistribution and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the latter. In particular, randomized (0, m, s)-nets in basebproduce unbiased estimates of the integral, have a variance that tends to zero faster than 1/nfor any square integrable integrand and have a variance that for finitenis never more thane?2.718 times as large as the Monte Carlo variance. Lower bounds thaneare known for special cases. Some very important (t, m, s)-nets havet>0. The widely used Sobol' sequences are of this form, as are some recent and very promising nets due to Niederreiter and Xing. Much less is known about randomized versions of these nets, especially ins>1 dimensions. This paper shows that scrambled (t, m, s)-nets enjoy the same properties as scrambled (0, m, s)-nets, except the sampling variance is guaranteed only to be belowbt[(b+1)/(b−1)]stimes the Monte Carlo variance for a least-favorable integrand and finiten. 相似文献
5.
《Finite Fields and Their Applications》2002,8(4):444-454
Until now, the concept of digital (t,m,s)-nets is the most powerful concept for the construction of low-discrepancy point sets in the s-dimensional unit cube. In this paper we consider a special class of digital nets over 2, the so-called shift nets introduced by W. Ch. Schmid, and give bounds for the quality parameter t of such nets. 相似文献
6.
Shu Tezuka 《Mathematica Slovaca》2009,59(3):379-386
In this paper, we consider Owen’s scrambling of an (m−1, m, d)-net in base b which consists of d copies of a (0, m, 1)-net in base b, and derive an exact formula for the gain coefficients of these nets. This formula leads us to a necessary and sufficient
condition for scrambled (m − 1, m, d)-nets to have smaller variance than simple Monte Carlo methods for the class of L
2 functions on [0, 1]
d
. Secondly, from the viewpoint of the Latin hypercube scrambling, we compare scrambled non-uniform nets with scrambled uniform
nets. An important consequence is that in the case of base two, many more gain coefficients are equal to zero in scrambled
(m − 1, m, d)-nets than in scrambled Sobol’ points for practical size of samples and dimensions.
相似文献
7.
Summary We prove upper bounds on the star discrepancy of digital (t, m, 2)-nets and (t, 2)-sequences over Z2. The main tool is a decomposition lemma for digital (t, m, 2)-nets, which states that every digital (t, m, 2)-net is just the union of 2tdigitally shifted digital (0, m - t, 2)-nets. Using this result we generalize upper bounds on the star discrepancy of digital (0, m, 2) -nets and (0, 2) -sequences. 相似文献
8.
Point sets and sequences with small discrepancy 总被引:17,自引:0,他引:17
Prof. Dr. Harald Niederreiter 《Monatshefte für Mathematik》1987,104(4):273-337
A systematic theory of a class of point sets called (t, m, s)-nets and of a class of sequences called (t, s)-sequences is developed. On the basis of this theory, point sets and sequences in thes-dimensional unit cube with the smallest discrepancy that is currently known are constructed. Various connections with other areas arise in this work, e.g. with orthogonal latin squares, finite projective planes, finite fields, and algebraic coding theory. Applications of the theory of (t, m, s)-nets to two methods for pseudorandom number generation, namely the digital multistep method and the GFSR method, are presented. Several open problems, mostly of a combinatorial nature, are stated.The author wants to thank the Universität Hannover (West Germany) for its hospitality during the period when most of this research was carried out. The results of this paper were presented at the Colloquium on Irregularities of Partitions at Fertöd (Hungary), July 7–11, 1986. 相似文献
9.
《Journal of Computational and Applied Mathematics》1997,87(1):169-193
We consider a simplified mathematical model of the Boltzmann equation which was introduced by Kac. A quasi-Monte-Carlo particle simulation using (t, m, s)-nets is described. The particle movement is shown to be an evaluation of the volume of a subset of I4=[0,1)4. An error bound for quasi-Monte-Carlo approximation of the volume of a generalized quadrant set is derived, when a (t, m, s)-net is used. Convergence of the simulation is proved when the particles are reordered according to their velocity in every time step. Quasi-Monte-Carlo and Monte-Carlo particle simulations are compared in computational experiments. The results indicate that quasi-Monte-Carlo simulation outperforms standard Monte-Carlo approaches. 相似文献
10.
Takashi Goda 《Archiv der Mathematik》2014,103(4):389-398
We give an explicit construction of two-dimensional point sets whose L p discrepancy is of best possible order for all \({1 \le p \le \infty}\) . It is provided by folding Hammersley point sets in base b by means of the b-adic baker’s transformation which has been introduced by Hickernell (Monte Carlo and quasi-Monte Carlo methods. Springer, Berlin, 274–289, 2002) for b = 2 and Goda, Suzuki, and Yoshiki (The b-adic baker’s transformation for quasi-Monte Carlo integration using digital nets. arXiv:1312.5850 [math:NA], 2013) for arbitrary \({b \in \mathbb{N}}\) , \({b \ge 2}\) . We prove that both the minimum Niederreiter–Rosenbloom–Tsfasman weight and the minimum Dick weight of folded Hammersley point sets are large enough to achieve the best possible order of L p discrepancy for all \({1 \le p \le \infty}\) . 相似文献
11.
Horst Trinker 《Designs, Codes and Cryptography》2011,60(2):101-121
The Plotkin bound and the quadratic bound for codes and (t, m, s)-nets can be obtained from the linear programming bound using certain linear and quadratic polynomials, respectively. We
extend this approach by considering cubic and higher degree polynomials to find new explicit bounds as well as new non-existence
results for codes and (t, m, s)-nets. 相似文献
12.
The theory of (t, m, s)-nets is useful in the study of sets of points in the unit cube with small discrepancy. It is known that the existence of a (0, 2,s)-net in baseb is equivalent to the existence ofs–2 mutually orthogonal latin squares of orderb. In this paper we generalize this equivalence by showing that fort0 the existence of a (t, t+2,s)-net in baseb is equivalent to the existence ofs mutually orthogonal hypercubes of dimensiont+2 and orderb. Using the theory of hypercubes we obtain upper bounds ons for the existence of such nets. Forb a prime power these bounds are best possible. We also state several open problems.This author would like to thank the Mathematics Department of the University of Tasmania for its hospitality during his sabbatical when this paper was written. The same author would also like to thank the NSA for partial support under grant agreement # MDA904-87-H-2023.This author's research was supported by a grant from the Commonwealth of Australia through the Australian Research Council. 相似文献
13.
Jennifer Seberry Wallis 《Journal of Combinatorial Theory, Series A》1976,21(2):188-195
Given any natural number q > 3 we show there exists an integer t ? [2log2(q ? 3)] such that an Hadamard matrix exists for every order 2sq where s > t. The Hadamard conjecture is that s = 2.This means that for each q there is a finite number of orders 2υq for which an Hadamard matrix is not known. This is the first time such a statement could be made for arbitrary q.In particular it is already known that an Hadamard matrix exists for each 2sq where if q = 2m ? 1 then s ? m, if q = 2m + 3 (a prime power) then s ? m, if q = 2m + 1 (a prime power) then s ? m + 1.It is also shown that all orthogonal designs of types (a, b, m ? a ? b) and (a, b), 0 ? a + b ? m, exist in orders m = 2t and 2t+2 · 3, t ? 1 a positive integer. 相似文献
14.
The energy of a graph is the sum of the moduli of the eigenvalues of its adjacency matrix. We study the energy of integral circulant graphs, also called gcd graphs, which can be characterized by their vertex count n and a set D of divisors of n in such a way that they have vertex set Zn and edge set {{a,b}:a,b∈Zn,gcd(a-b,n)∈D}. Using tools from convex optimization, we analyze the maximal energy among all integral circulant graphs of prime power order ps and varying divisor sets D. Our main result states that this maximal energy approximately lies between s(p-1)ps-1 and twice this value. We construct suitable divisor sets for which the energy lies in this interval. We also characterize hyperenergetic integral circulant graphs of prime power order and exhibit an interesting topological property of their divisor sets. 相似文献
15.
(t,m,s)-Nets were defined by Niederreiter [Monatshefte fur Mathematik, Vol. 104 (1987) pp. 273–337], based on earlier work by Sobol’ [Zh. Vychisl Mat. i mat. Fiz, Vol. 7 (1967) pp. 784–802], in the context of quasi-Monte Carlo methods of numerical integration. Formulated in combinatorial/coding theoretic terms a binary linear (m−k,m,s)2-net is a family of ks vectors in F2m satisfying certain linear independence conditions (s is the length, m the dimension and k the strength: certain subsets of k vectors must be linearly independent). Helleseth et al. [5] recently constructed (2r−3,2r+2,2r−1)2-nets for every r. In this paper, we give a direct and elementary construction for (2r−3,2r+2,2r+1)2-nets based on a family of binary linear codes of minimum distance 6.Communicated by: T. Helleseth 相似文献
16.
Let Ωm be the set of partitions, ω, of a finite m-element set; induce a uniform probability distribution on Ωm, and define Xms(ω) as the number of s-element subsets in ω. We alow the existence of an integer-valued function n=n(m)(t), t?[0, 1], and centering constants bms, 0?s? m, such that converges to the ‘Brownian Bridge’ process in terms of its finite-dimensional distributions. 相似文献
17.
Quasi-Monte Carlo (QMC) sampling has been developed for integration over \([0,1]^s\) where it has superior accuracy to Monte Carlo (MC) for integrands of bounded variation. Scrambled net quadrature allows replication-based error estimation for QMC with at least the same accuracy and for smooth enough integrands even better accuracy than plain QMC. Integration over triangles, spheres, disks and Cartesian products of such spaces is more difficult for QMC because the induced integrand on a unit cube may fail to have the desired regularity. In this paper, we present a construction of point sets for numerical integration over Cartesian products of s spaces of dimension d, with triangles (\(d=2\)) being of special interest. The point sets are transformations of randomized (t, m, s)-nets using recursive geometric partitions. The resulting integral estimates are unbiased, and their variance is o(1 / n) for any integrand in \(L^2\) of the product space. Under smoothness assumptions on the integrand, our randomized QMC algorithm has variance \(O(n^{-1 - 2/d} (\log n)^{s-1})\), for integration over s-fold Cartesian products of d-dimensional domains, compared to \(O(n^{-1})\) for ordinary MC. 相似文献
18.
Let x?Sn, the symmetric group on n symbols. Let θ? Aut(Sn) and let the automorphim order of x with respect to θ be defined by where xθ is the image of x under θ. Let αg? Aut(Sn) denote conjugation by the element g?Sn. Let where s and k are positive integers and denotes a divides b. Further h(s, k : n) ≡ b(1; s, k : n), where 1 denotes the identity automorphim. If g?Sn let c = f(g, s) denote the number of symbols in g which are in cycles of length not dividing the integer s, and let gs denote the product of all cycles in g whose lengths do not divide s. Then gs moves c symbols. The main results proved are: (1) recursion: if n ? c + 1 and t = n ? c ? 1 then (2) reduction: b(g; s, 1 : c)h(s, 1 : i) = b(g; s, 1 : i + c); (3) distribution: let D(θ, n) ≡ {(k, b) : k?Z+ and b = b(θ; 1, k : n) ≠ 0}; then D(θ, m) = D(φ, m) ∨ m ? N = N(θ, φ) iff θ is conjugate to φ; (4) evaluation: the number of cycles in gss of any given length is smaller than the smallest prime dividing s iff b(gs; s, 1 : c) = 1. If g = (12 … pm)t and then . 相似文献
19.
We determine all pairs of Stolarsky means (E r,s , E k,m ) such that G o (E r,s , E k,m ) = G, where G = E 0,0 is the geometric mean. The convergence of the sequences of iterates of the mean-type mapping (E r,s , E k,m ) to the mapping (G, G) is considered. An application to a functional equation is given. 相似文献
20.
A study is made of the function H(s, z) defined by analytic continuation of the Dirichlet series H(s, z) = Σn=1∞n?sΣm=1nm?z, where s and z are complex variables. For each fixed z it is shown that H(s, z) exists in the entire s-plane as a meromorphic function of s, and its poles and residues are determined. Also, for each fixed s ≠ 1 it is shown that H(s, z) exists in the entire z-plane as a meromorphic function of z, and again its poles and residues are determined. Two different representations of H(s, z) are given from which a reciprocity law, H(s, z) + H(z, s) = ζ(s) ζ(z) + ζ(s + z), is deduced. For each integer q ≥ 0 the function values H(s, ?q) and H(?q, s) are expressed in terms of the Riemann zeta function. Similar results are also obtained for the Dirichlet series T(s, z) = Σn=1∞n?sΣm=1nm?z (m + n)?1. Applications include identities previously obtained by Ramanujan, Williams, and Rao and Sarma. 相似文献