MinT - Salzburg Tables

Salzburg Tables

In [1] and [2, Sect. 4.4] a construction for digital (t, m, s)-nets over F_b based on formal Laurent series over F_b is proposed. Given polynomials g₁,…, g_s and f, all over F_b, deg g_i < m, and deg f = m, we consider the Laurent expansions

$\displaystyle {\frac{{g_{i}(x)}}{{f(x)}}}$ = $\displaystyle \sum_{{w=1}}^{{\infty}}$ u_w⁽ⁱ⁾x^−w

for i = 1,…, s and define the elements c_jk⁽ⁱ⁾ of the generator matrices C⁽ⁱ⁾ by c_jr⁽ⁱ⁾ := u_j+r⁽ⁱ⁾. Now C⁽¹⁾,…,C^(s) define a digital (t, m, s)-net with

t ≤ m + 1 – min $\displaystyle \sum_{{i=1}}^{{s}}$ (1 + deg h_i),

where the minimum extends over all nonzero s-tuples (h₁,…, h_s) for which f divides $\sum_{{i=1}}^{{s}}$ g_ih_i.

Obviously, the quality of the resulting net depends on the polynomials f, g₁,…, g_s used in the construction. Few theoretical results are known about choosing them properly, so one has to resort to a search. A crucial simplification is the restriction to g_i = gⁱ⁻¹ mod f for some g ∈ F_b[x].

A first attempt to find optimal polynomials f and g was made in [3], however the parameter range was restricted to b = 2, m ≤ 20 for s = 3, 4, and m ≤ 10 for larger dimensions.

In [4] the parameter range was extended to b = 2, m ≤ 25 and s ≤ 15. A search was performed over all possible g’s with f fixed to f (x) = x^m, because in this case arithmetic modulo f becomes trivial. The tables of t-parameters found with this approach became known as “Salzburg Tables”.

In [5] the parameter range was extended to b = 2, m ≤ 39 and s ≤ 50. In addition to that, an irreducible polynomial f was used instead of f (x) = x^m. This choice complicates determining the t-parameter, but leads to lower values.

References

[1]	Harald Niederreiter. Low-discrepancy point sets obtained by digital constructions over finite fields. Czechoslovak Mathematical Journal, 42:143–166, 1992. MR1152177 (93c:11055)
[2]	Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods, volume 63 of CBMS-NSF Regional Conference Series in Applied Mathematics. SIAM Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1992. MR1172997 (93h:65008)
[3]	T. Hansen, Gary L. Mullen, and Harald Niederreiter. Good parameters for a class of node sets in quasi-Monte Carlo integration. Mathematics of Computation, 61:225–234, 1993.
[4]	Gerhard Larcher, A. Lauß, Harald Niederreiter, and Wolfgang Ch. Schmid. Optimal polynomials for (t, m, s)-nets and numerical integration of multivariate Walsh series. SIAM Journal on Numerical Analysis, 33(6):2239–2253, 1996. doi:10.1137/S0036142994264705
[5]	Wolfgang Ch. Schmid. Improvements and extensions of the “Salzburg Tables” by using irreducible polynomials. In Harald Niederreiter and Jerome Spanier, editors, Monte Carlo and Quasi-Monte Carlo Methods 1998, pages 436–447. Springer-Verlag, 2000.

Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Salzburg Tables.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_NSalzburgTable.html

Show usage of this method