NXLegacy

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 &gt 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, 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, 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
s.. - dimension = no. of matrices
m.. - log no. of points, precision, size of matrices

File format:

First entry : m
Second entry : s
Next s*m entries : row vectors of the first, second,..., s-th matrix, encoded as decimal number. The vector consists of the digits of the b-ary expansion of the number, most significant bits corresponding to the initial coordinates of the vector. (E.g. b = 2, m = 8: entry 11 <-> row vector [0 0 0 0 1 0 1 1] )
The matrices are such that the b-ary fractional digit vectors of the points are obtained by multiplying the s matrices with the same b-ary (index) digit vector from the right.

All of the following matrices are constructed in base b = 2, i.e. are elements of GF(2)^(m * m).
nxs04m42, nxs05m42, nxs06m42, nxs07m42, nxs08m42, nxs09m32,
nxs10m32, nxs11m32, nxs12m32, nxs13m32, nxs14m32, nxs15m32,
nxs16m32, nxs17m32, nxs18m32, nxs19m32, nxs20m32, nxs21m32,
nxs22m32, nxs23m32, nxs24m32, nxs25m32, nxs26m32, nxs27m32,
nxs28m32, nxs29m32, nxs30m32, nxs31m32, nxs32m32

 (Note: individual file download not supported, but the following tar-zipped archive of all the files can be downloaded: )

All files in one .tgz archive : nxsmats.tgz
For t-values look here. Each row is one dimension, m increases with the column number (m grows across, s down). Also a transposed version is available as well as one transposed (i.e. each column is one dimension) and with propagation rules applied.

Also take a look at the MinT database of t-values produced by my colleagues in Salzburg.

Application Caveats

For 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, Links

The 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.
(ATTENTION: As Thomas Kollig thankfully pointed out, there had been an error in the libseq-formatted files provided earlier: the intended original matrices would have been like the entries in the files but with 0 and 1 interchanged.)
Under this link you can get an example C++ program (MS Windows version here) implementing the generation of the points (not the matrices!) (tested under Linux (g++) and Windows (cygwin) ). NOTE: you should download the latest version of the fkmats.tgz matrices as well, as the matrices included in the packages may have been improved/corrected/expanded.

Two further HIGHDIMENSIONAL matrices in the libseq format:
base 16, dimension 63, matrix size 30, t at most 6 : fkmat63b16
base 64, dimension 511, matrix size 32, t at most 28 : fkmat511b64
(Note: the TABLE_LENGTH in `options.h' of `libseq' may have to be increased to use this matrices!)

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.
After the script is loaded into the KASH system, type

calc_c(m,s);
replacing m and s with your desired parameters. The matrices are stored in the variable c, an s by m by m array, and output into the file "matout" in the above format.

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 data

Have 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

(Note: Unsupported, i.e., not working yet:) Here is a nice 3D interactive stereo scatter plot of a Niederreiter-Xing sequence (needs JavaScript capabilities).

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.

Institute homepage

Comments