Geordnete Orthogonale Arrays für Quasi-Monte Carlo Methoden

Die von Niederreiter entwickelte Theorie der (t, m, s)-Netze ist einer der erfolgreichsten Ansätze zur Erzeugung von niedrigdiskrepanten Punktmengen im s-dimensionalen Einheitswürfel. Diese Punktmengen spielen eine zentrale Rolle bei Quasi-Monte Carlo Methoden, insbesondere bei der Berechnung von hochdimensionalen Integralen wie sie zum Beispiel in der Finanzmathematik auftreten. Ein großes Problem für die Anwender ist die unüberschaubare Anzahl verschiedener Konstruktionen von (t, m, s)- Netzen. Zusätzliche Schwierigkeiten bereitet die enge Verknüpfung zu anderen mathematischen Objekten wie linearen Codes oder orthogonalen Arrays. Durch die Einführung von geordneten orthogonalen Arrays (OOAs) konnten wir diese verschiedenen Objekte in ein einheitliches Schema bringen. OOAs sind endliche kombinatorische Strukturen, die Netze, orthogonale Arrays und (aufgrund der Dualitätstheorie) auch lineare Codes als Teilklassen enthalten. Viele der besten derzeit bekannten Netze können nicht direkt, sondern nur aus linearen Codes oder anderen Netzen konstruiert werden. Durch die Einschränkung auf diese Teilklassen von OOAs wird man jedoch keine optimalen Netze erhalten. Bessere Ergebnisse kann man nur dann erzielen, wenn man die gesamte, umfassende Struktur der OOAs verwendet. Dadurch werden wir den Parameterbereich von (t, m, s)-Netzen viel genauer bestimmen können, als dies früher möglich war.

Die im Projekt gezeigten Resultate gehören zu den Forschungsgebieten der Codierungstheorie und der Quasi- Monte-Carlo-Methoden. Konkret beschäftigen wir uns mit Existenz und Nicht-Existenz von Codes, geordneten Codes, orthogonalen Arrays und (t,m,s)-Netzen. Zu diesem Zweck entwickeln wir die Online-Datenbank "MinT" (mint.sbg.ac.at), die mögliche Parameter berechnet und dem Benutzer zur Verfügung stellt. Während Codes überall dort Anwendung finden, wo es um die Speicherung oder Übertragung von Daten geht (beispielsweise auf CDs), liegt der Anwendungsbereich von orthogonalen Arrays, die ihren Ursprung in der Statistik haben, vor allem im Design von Experimenten und Tests (z.B. können sie beim Test von Computersoftware Verwendung finden). Zwischen Codes und orthogonalen Arrays besteht über eine Dualitätstheorie ein enger Zusammenhang. Die Theorie der (t,m,s)-Netze gehört zu den Quasi-Monte-Carlo-Methoden. Bei diesen Netzen handelt es sich um "gut verteilte" Punktmengen im s-dimensionalen Raum, die bei der numerischen Auswertung von (hochdimensionalen) Integralen verwendet werden. Verallgemeinert man das Konzept eines Codes und betrachtet man so genannte geordnete Codes, so überträgt sich die Dualität von Codes und orthogonalen Arrays auf eine Dualität von diesen geordneten Codes und (t,m,s)-Netzen. Es ist ein nichttriviales Problem, die Parameter zu bestimmen, für die Codes, orthogonale Arrays, geordnete Codes und (t,m,s)-Netze überhaupt existieren können. Eine der stärksten, aber nicht expliziten Schranken, ist die lineare Optimierungsschranke (LP-Schranke). In unserer Arbeit leiten wir aus ihr neue explizite Schranken her, die eine Verschärfung einiger bekannter Schranken ergeben. Zur Konstruktion von neuen geordneten Codes und (t,m,s)-Netzen wurden eine Vielzahl von Methoden aus der Codierungstheorie und der Theorie der orthogonalen Arrays entsprechend verallgemeinert. All diese neuen Methoden wurden in MinT eingepflegt, in einem großen Parameterbereich durchgerechnet und die Resultate damit online zu Verfügung gestellt. Dadurch ergeben sich für wissenschaftliche Anwender neue Möglichkeiten, die bekannten wie auch aktuelle Resultate zu visualisieren, zu verknüpfen und einfach auf diese zuzugreifen.