Ordered Orthogonal Arrays in Quasi-Monte Carlo Methods

The theory of (t, m, s)-nets developed by Niederreiter is one of the most successful approaches to point sets in the s-dimensional unit cube with very small discrepancy. Such point sets are of great practical interest, in particular for building quasi-Monte Carlo cubature rules. These rules are successfully used for evaluating high dimensional integrals arising in many applications, for instance financial mathematics. A problem for the practitioner is that an overwhelming variety of different constructions for (t, m, s)-nets exists. Choosing an optimal net is further complicated by the fact that the existence of nets is often linked to other mathematical objects, e.g. to linear codes or orthogonal arrays. The connection between these different objects is made explicit by the introduction of ordered orthogonal arrays (OOAs). OOAs are finite combinatorial structures which contain nets as well as orthogonal arrays as subclasses. Duality establishes the connection to linear codes. Many of the best nets known today are not constructed directly, but are derived from linear codes or other nets using so-called propagation rules. However, the restriction to these special subclasses of OOAs prevents the construction of optimal nets. Better results are available only if one uses the entire and rich structure of OOAs. Our project aims at obtaining new lower and upper bounds on the possible parameters of (t, m, s)-nets by exploiting all possible constructions and propagation rules available in the framework of OOAs.

The results achieved within the project belong to the research areas of coding theory and quasi-Monte Carlo methods. Specifically, we deal with existence and non-existence results for codes, ordered codes, orthogonal arrays, and (t,m,s)-nets. To this end, we develop the online database "Mint" (mint.sbg.ac.at), which calculates potential parameters and provides them to the scientific community. While codes are used for storing and transmitting data over noisy channels (e.g. Reed-Solomon codes are used on Compact Discs), an important application of orthogonal arrays is the design of experiments and tests (e.g. for testing computer software). There is a close connection between codes and orthogonal arrays via a duality theory. The theory of (t,m,s)-nets is a type of quasi-Monte Carlo methods. These nets are "well distributed" point sets in the s-dimensional cube, which find their main application in the numerical integration of high-dimensional integrals. Generalizing the concept of codes and considering so-called ordered codes, the duality of codes and orthogonal arrays carries over to a duality of ordered codes and (t,m,s)-nets. It is a non-trivial problem to determine the parameters for which codes, orthogonal arrays, ordered codes and (t,m,s)-nets do and do not exist. One of the strongest (though non-explicit) bounds on the parameters of these mathematical objects is the linear programming (LP) bound. In our work we derive explicit bounds from the LP bound, which improve a number of known bounds. In order to construct new ordered codes and (t, m, s)-nets, a wide variety of methods from coding theory and the theory of orthogonal arrays have been generalized. All these new methods have been included in Mint, calculated for a large range of parameters, and the results have made available online. This gives new opportunities for scientific users, who can access, visualize, and combine these results easily.