TU Darmstadt / ULB / TUprints

Ein Framework zur Berechnung der Hermite-Normalform von großen, dünnbesetzten, ganzzahligen Matrizen

Theobald, Patrick (2001)
Ein Framework zur Berechnung der Hermite-Normalform von großen, dünnbesetzten, ganzzahligen Matrizen.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
ptheobald_dissertation.pdf
Copyright Information: In Copyright.

Download (4MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Ein Framework zur Berechnung der Hermite-Normalform von großen, dünnbesetzten, ganzzahligen Matrizen
Language: German
Referees: Buchmann, Dr.Prof. Johannes ; Bosma, Dr.Prof. Wieb
Advisors: Buchmann, Dr.Prof. Johannes
Date: 12 June 2001
Place of Publication: Darmstadt
Date of oral examination: 12 December 2000
Abstract:

Unter der Hermite--Normalform (abgekürzt HNF) einer ganzzahligen Matrix A versteht man (vereinfacht dargestellt) eine zu A äquivalente obere Dreiecksmatrix H, bei der die Einträge oberhalb der Diagonalen modulo dem zugehörigen Diagonalelement reduziert sind, d.h. betragsmäßig zwischen Null und dem jeweiligen Diagonalelement liegen. Eine Matrix A ist zur einer Matrix H genau dann äquivalent, wenn eine ganzzahlige, unimodulare Matrix T existiert, so daß gilt A x T = H. Während der letzten Jahre wurden eine Vielzahl von Algorithmen zur Berechnung der HNF entwickelt, angefangen bei den Algorithmen von Charles Hermite bis hin zu den Algorithmen von George Havas. In der Praxis wird man bei der Berechnung der HNF von großen, ganzzahligen Matrizen auf einer speziellen, festgelegten Maschine mit dem Problem konfrontiert, daß während der Durchführung der Berechnung zunächst die Eintragsdichte, d.h. der prozentuale Anteil der von Null verschiedenen Elemente unter den Einträgen, und dann die Eintragsgröße der entstehenden Zwischeneinträge in unkontrollierter Art und Weise anwachsen. Dies führt zu einem hohen Speicherplatzverbrauch und mündet schließlich im Abbruch der Berechnung. Um diesem Phänomen zu begegnen, wurden vorrangig für dichtbesetzte Matrizen eine Vielzahl von optimierten Algorithmen entwickelt. Für die Matrizen, die im Kontext der Klassengruppenberechnung entstehen, reichen diese Optimierungen nicht aus, d.h. es ist nicht möglich, auf der uns zur Verfügung stehenden Hardware die HNF dieser Matrizen zu berechnen. Vor dem Hintergrund dieser Problemstellung ist die vorliegende Arbeit entstanden. Die Idee dieser Arbeit basiert auf der Beobachtung, daß sich unterschiedliche ``einfache'' (aus der Literatur bekannte) HNF--Algorithmen angewendet auf die gleiche Eingabematrix in Bezug auf ihr Laufzeitverhalten, d.h. die Entwicklung des Speicherplatzverbrauchs, die Entwicklung der Eintragsdichte, die Entwicklung der Eintragsgröße u.a., unterschiedlich verhalten. Wenn also nicht ein einzelner der ``einfachen'' HNF--Algorithmen in der Lage ist, die HNF einer dünnbesetzen, ganzzahligen Matrix unter Berücksichtigung der zur Verfügung stehenden Hardwareressourcen zu berechnen, dann könnte es einer geeigneten Kombination dieser Algorithmen gelingen. Eine solche Kombination ``einfacher'' HNF--Algorithmen wird im Rahmen dieser Arbeit als Hybrid--HNF—Algorithmus bezeichnet und arbeitet prinzipiell gemäß der folgenden Vorgehensweise: Die HNF--Berechnung startet mit einem ``einfachen'' HNF--Algorithmus, der aufgrund der aktuellen Kennwerte der Eingabematrix, d.h. der Eintragsdichte, der Eintragsverteilung, der Eintragsgröße u.a., als geeignet erachtet wird. Während der Durchführung der Berechnung werden die Veränderungen der Kennwerte der (Zwischen-)Matrix protokolliert. Zu dem Zeitpunkt, zu dem ein anderer ``einfacher'' HNF--Algorithmus aufgrund der veränderten Situation besser geeignet ist, als der bisher verwendete HNF--Algorithmus, paßt man die Verarbeitungsstrategie den veränderten Bedingungen an. Dazu beendet man die Berechnung mit dem aktuellen ``einfachen'' HNF--Algorithmus und führt die Berechnung auf der zu diesem Zeitpunkt vorliegenden Zwischenmatrix mit dem neuen, besser geeigneten HNF--Algorithmus fort. Die Untersuchung dieser Idee und ihre Umsetzung ist Gegenstand dieser Arbeit. Um ``einfache'' HNF--Algorithmen zu Hybrid--HNF-Algorithmen kombinieren zu können, wurde ein geeignetes C++ Framework entwickelt. Grundlage dieses Frameworks ist zum einen eine Systematik der bekannten ``einfachen'' HNF--Algorithmen und zum anderen ein geeignetes C++ Klassendesign zur Realisierung von Matrixoperationen. Ein weiterer Bestandteil dieser Arbeit ist eine Arbeitsanweisung, die veranschaulicht, wie das C++ Framework auf eine spezielle Problemstellung hin anzuwenden ist. Dabei wird dargelegt, welche Überlegungen und Schritte notwendig sind, um einen angemessenen Hybrid--HNF--Algorithmus zu konstruieren. Zum Abschluß dieser Arbeit wird die Leistungsfähigkeit des Frameworks und damit der zugrundeliegenden Idee anhand von Hybrid--HNF--Algorithmen illustriert, die für Matrizen, die im speziellen Umfeld der Klassengruppenberechnung entstehen, und für eine vorgegebene Hardware entwickelt wurden. Umfangreiche Laufzeittabellen illustrieren die Effizienz und somit die Leistungsfähigkeit. Die aktuellen Rekorde im Bereich der Klassengruppen wurden mit Hilfe der in dieser Arbeit entwickleten Hybrid--HNF--Algorithmen berechnet.

Alternative Abstract:
Alternative AbstractLanguage

Briefly speaking the Hermite normal form (abbreviated: HNF) of an integer matrix A is an upper triangular matrix H, where the entries above the diagonal are reduced modulo the specific diagonal element: which means, their value is in the range between zero and the specific diagonal element. A matrix A is equivalent to a matrix H if and only if there is an unimodular matrix T with A x T = H. During the last years a lot of algorithms for computing the HNF were developed, starting with the algorithms of Charles Hermite to the algorithms of George Havas. In the process of HNF computations with large, integer matrices on a specific machine, one is confronted with the following problem: In the beginning, the density of the non--zero entries and later also the entry size of the intermediate entries are growing in an uncontrollable manner. In general this leads to a very intense use of storage and finally to the abortion of the computation. In order to solve this problem a number of optimized algorithms were developed mainly for dense matrices. However for matrices, which are generated in the context of class group computations, these optimizations are not sufficient. I.e., it is not possible to compute the HNF of these matrices with the current hardware available. This is the motivation of this thesis. The discussion in this thesis is based on the observation, that different ``simple'' HNF algorithms (known from literature), if applied to the same matrix, act differently at runtime with respect to storage use and development of density. If it is not possible for a single one of the ``simple'' HNF algorithms to compute the HNF of an integer matrix under the restrictions of the available hardware resources, a useful combination of such algorithms could succeed. In the following such a combination is called hybrid HNF algorithm and would function as follows: The computation is started with a ``simple'' HNF algorithm, which is chosen based on the actual parameters of the matrix, i.e., density, entry distribution and entry size. During the process of the computation we keep track of the changes of the parameters of the matrix. Whenever a different ``simple'' HNF algorithm is more suitable than the one used so far (because of the changed parameters) one switches to the new ``simple'' HNF algorithm. The analysis of this idea and its implementation are the topic of this thesis. In order to combine ``simple'' HNF algorithms to a hybrid HNF algorithm a C++ framework is introduced. For that purpose a system of known ``simple'' HNF algorithms and a suitable C++ class design for the implementation of matrix operations is developed. In addition to that instructions on how the C++ framework has to be applied to a special problem are given, i.e., it is shown what has to be considered for the construction of an efficient hybrid HNF algorithm. As conclusion of this thesis the functionality of our framework is demonstrated in the special area of class group computations. The current records in the area of class groups were computed with the help of these hybrid HNF algorithms.

English
URN: urn:nbn:de:tuda-tuprints-1337
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:20
Last Modified: 08 Jul 2020 22:41
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/133
PPN:
Export:
Actions (login required)
View Item View Item