in the repository
Title data
Vogel, Heiko:
Gitterbasenreduktion mit Random Sampling und heuristischen Erweiterungen.
Bayreuth
,
2011
(
Doctoral thesis,
2011
, University of Bayreuth, Faculty of Mathematics, Physics and Computer Sciences)
![[thumbnail of hvogel_diss.pdf]](https://epub.uni-bayreuth.de/style/images/fileicons/application_pdf.png) |
|
||||||||
|
Download (1MB)
|
|||||||||
![[thumbnail of rasa_1.44.tar.gz]](https://epub.uni-bayreuth.de/style/images/fileicons/application_x-gzip.png) |
|
||||||||
|
Download (24MB)
|
Abstract
Diese Dissertation beschäftigt sich mit dem mathematischen Teilgebiet der Gitterbasenreduktion. Aufbauend aus den Erkenntnissen der Diplomarbeit "Gitterbasenreduktion mit Random Sampling" werden verschiedene Modifikationen am ursprünglichen LLL- bzw. BKZ-Verfahren vorgenommen: Es wird der von C. Schnorr entwickelte Ansatz, den LLL-Austauschschritt um Tiefeneinfügungen zu erweitern, aufgegriffen und eine alternative Methode zum Basisaustausch für das BKZ-Verfahren vorgestellt. Ferner werden zwei unterschiedliche Verfahren von A. Wassermann und P. Nguyen zum Abschneiden von Enumerationsbäumen beschrieben. Die Random Sampling Strategie von Schnorr wurde überarbeitet, um ein schlechtes GSA-Verhalten des Gitters zu berücksichtigen und eine neuartige Strategie von Buchmann und Ludwig wurde implementiert, bei der das GSA-Verhalten vollkommen irrelevant ist. Schließlich wird ein grundlegendes, heuristisches Bewertungskonzept für Gittervektoren entwickelt, das im Rahmen eines von T. Vidick und P. Nguyen beschriebenen Siebverfahrens, Anwendung findet. Mit Hinblick auf die Qualität der erreichten Gitter-Reduktion für schwierige Market-Split-Probleme in Dimensionen ≈ 120, liefern diese neuen Methoden hervorragende Ergebnisse in äußerst kurzer Zeit (ca. 5 Stunden auf einem 3 GHz Rechner). Auch für Problemdimensionen > 500 sind die Resultate durchaus noch zufriedenstellend - allerdings ist hierbei der Rechenaufwand (> 7 Tage) nicht mehr zu vernachlässigen. Im Vergleich mit dem kommerziellen Programm CPLEX, das einen völlig anderen Ansatz zur Lösung von ganzzahlig-linearen Gleichungssystemen verfolgt, konnten sogar sehr gute Ergebnisse erzielt werden.
Abstract in another language
This dissertation describes the mathematical subject concerned with lattice basis reduction and analyzes several algorithms which are involved in solving lattice based problems. Stacked on the scientific findings of the diploma thesis "Gitterbasenreduktion mit Random Sampling" several modifications of the famous LLL-algorithm and the generalized BKZ-reduction are introduced: C. Schnorr’s method for extending the Lovasz step with deep insertions and a modified basis replacement routine for the enumeration step, which was first described by H. Hörner. Further, two different cutting techniques are explained, which allow to decrease the size of the enumeration tree. These techniques originate from A. Wassermann and P. Nguyen. Schnorr’s Random Sampling strategy is modified in order to deal with lattices, which have a bad GSA behaviour and an approach from Buchmann and Ludwig is implemented where the GSA behaviour gets totally irrelevant. Finally a heuristical evaluation concept for lattice vectors is developed and implemented in form of a modified sieve algorithm, which originates from Ajtaj, Kumar, Sivakumar (AKS) and has been extensively examined by T. Vidick and P. Nguyen afterwards. Regarding the quality of the achieved lattice reductions for hard market split problems in dimensions ≈ 120 these new methods produce excellent results in short time (about 5 hours on a machine with 3 GHz). Even for problem dimensions > 500 the findings are still quite satisfying, though the computation amount (> 7 days) is not negligible anymore. In comparison with the commercial program CPLEX, which uses completely different methods for solving integer linear programs, the results are remarkably very good and motivate further investigations in the field of lattice reduction.
Further data
| Item Type: | Doctoral thesis (No information) |
|---|---|
| Additional notes (visible to public): | msc: 05A99; msc: 06B99 |
| Keywords: | Ganzzahliges Gitter; Gitter <Mathematik>; Zufall; Abzählen; Heuristik; Ganzzahlig-Lineare Gleichungssysteme; Gitterbasenreduktion; Random Sampling; Siebverfahren; integer linear equation systems; lattice; lattice basis reduction; random sampling; heuristical sieve |
| DDC Subjects: | 500 Science > 510 Mathematics |
| Institutions of the University: | Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics Faculties Faculties > Faculty of Mathematics, Physics und Computer Science |
| Language: | German |
| Originates at UBT: | Yes |
| URN: | urn:nbn:de:bvb:703-opus-8963 |
| Date Deposited: | 25 Apr 2014 08:26 |
| Last Modified: | 25 Apr 2014 08:27 |
| URI: | https://epub.uni-bayreuth.de/id/eprint/326 |
Download Statistics