Theobald, Patrick (2001)
Ein Framework zur Berechnung der Hermite-Normalform von großen, dünnbesetzten, ganzzahligen Matrizen.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (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.

Frage zum Eintrag

Redaktionelle Details anzeigen