Niederreiter-Xing sequence implementation page Added Note: The following is mostly a direct copy of my old NX implementation pages. Data and KASH-scripts have not been updated for a long time, more recent scripts (in Magma) are available at the AGSIS subpage on this site.This site is subject to change. Please revisit to keep updated. Planned for next major update: kash script for Niederreiter-Özbudak sequences, according bibliography update Last updates: 2006-03-09 Minor update of kash script (tnx2 Anthony Senyard) 2004-11-30 Application Caveats (inspired by Prof.Mathe) 2004-07-16 (minor fixes and description expansion) 2003-05-18 fixed t-table description (was transposed) 2003-04-09 Bugfix (matters of format, not content) in libseq-formatted matrices fkmat511/63 (Dank an R.Schuerer), 2002-08-26, updated nxs??m?? and their t-values (Dank an A.Keller ) 2002-05-22, niedxing_v3.kash: improved comments, msdos/win capable (?), b > 2 implemented, but not working correctly -_- (yet:) 2002-03-07, bugfix re 0/1 transposition in fkmats 2001-08-17, added t-value table for matrices up to s=32) Maintained by Isabel.Pirsic@jku.at ## Papers## Preprints:- G. Pirsic, A software implementation of Niederreiter-Xing sequences.
*Monte Carlo and quasi-Monte Carlo methods, 2000 (Hong Kong),*434–445,*Springer, Berlin,*2002. [.ps- preprint here]
License Note: you can use anything provided by me on this page freely for academic use, it would, however, be courteous if you could attribute the contribution by citing the above reference in your paper.## Generator matrices of NX-sequences## Name convention: nxs..m..
nx - signifies Niederreiter/Xing construction ## File format:
First entry : m I.e., x_{i,n} = C_i · v_n, where C_i is the ith of s matrices, v_n is the input, the digit vector of n, lowest significant digit as first component, x_{i,n} the output, the (fractional) digit vector of the ith component of the nth point, most significant digit at first index. (Hope that helps...) All of the following matrices are constructed in base b = 2, i.e. are elements of GF(2)^(m * m). (
All files in one .tgz archive : nxsmats.tgz ## Application CaveatsFor non-specialists: the t-values can be interpreted e.g. as an exponential factor in the error bound of numerical integration. Furthermore it indicates how many points you should take at least for the theoretic bounds to make sense: if at matrix size m you have some t-value of, say, u, you should take at least b^u points. On a related note, since it may take some time, before reasonable quasi-equidistribution is attained, one thing you can do is to "shuffle" the points, i.e. reorder them. You could e.g. do this by multiplying all the matrices FROM THE RIGHT with ONE CHOSEN REGULAR MATRIX and then proceeding as below. There exist also some further techniques to improve the quality by some (possibly small) degrees that have recently been found by Rudolf Schuerer of Salzburg University (Austria). The main philosophy of this page is, however, to focus on providing the unadulterated matrices as produced by the algorithm. ## Sources, Programs, LinksThe above format is designed for calculating the t-value. For
calculating the actual points, the
file under this link is a tar-gzip
compressed collection of the above matrices for use with the
libseq-library of Ilja Friedel and Alexander Keller.
Two further HIGHDIMENSIONAL matrices in the libseq format: Please contact me at Isabel.Pirsic@jku.at if you need larger matrix sizes
( = more points = higher precision )
for any of the above dimensions/bases or any further clarification.
A KASH script
for generation of the matrices of the base 2 sequences in the above dimensions
is available under this link.
(Older versions: V2,V3)
This file (prototypes) is for variable declaration
and
this file (ffdata) holds function field data - here
is where you may add further high rational place count function fields.
All three files (niedxing_v?.kash, prototypes, ffdata) are required to
exist in the same directory (e.g. your KASH directory) for the script to
run correctly.
A C++ program is available on demand, for s at most 16. (However, I still don't trust it fully yet, so preferrably please use the above KASH script... ) ## Numbers, further dataHave a look at some numerical experiment results.An (uncommented, undocumented) implementation of chapter 5.6 ( about explicit towers of algebraic function fields) of the book of Niederreiter and Xing, "Rational Points on Curves over Finite Fields" can be found here. ## Pictures() Here is a nice 3D interactive stereo scatter plot
of a Niederreiter-Xing sequence (needs JavaScript capabilities).Note: Unsupported, i.e., not working yet:Almost unrelated (but pretty): a function plot (ca. 2M color postscript file) of (w-1)^4 = (v^3+1) over the complex plane, where x+i*y=v, z=abs(w) and color is arg(w). Observe three visible ramification points with different exponent d=3 (fourth is at infinity) and four leaves, therefore by the Hurwitz genus formula this is a Riemann surface topologically equivalent to a sphere with three handles (g=3). There is a triple zero of w at v=0. |