Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

Gitterbasenreduktion mit Random Sampling und heuristischen Erweiterungen

URN to cite this document: urn:nbn:de:bvb:703-opus-8963

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)

[img] PDF
hvogel_diss.pdf - Published Version
Available under License Creative Commons BY 3.0: Attribution .

Download (1MB)
[img] Archive (TGZ)
rasa_1.44.tar.gz - Published Version
Available under License Creative Commons BY 3.0: Attribution .

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

Downloads

Downloads per month over past year