Salzburg Tables

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

$\displaystyle {\frac{{g_{i}(x)}}{{f(x)}}}$ = $\displaystyle \sum_{{w=1}}^{{\infty}}$uw(i)xw

for i = 1,…, s and define the elements cjk(i) of the generator matrices C(i) by cjr(i) := uj+r(i). Now C(1),…,C(s) define a digital (t, m, s)-net with

tm + 1 – min$\displaystyle \sum_{{i=1}}^{{s}}$(1 + deg hi),

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

Obviously, the quality of the resulting net depends on the polynomials f, g1,…, gs 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 gi = gi−1 mod f for some gFb[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) = xm, 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) = xm. 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: 2008-04-04. http://mint.sbg.ac.at/desc_NSalzburgTable.html

Show usage of this method