Segmentierung und Optimierung von Algorithmen zu Problemen aus der Zahlentheorie
 

Zusatz zum Titel:
Inaugural-Dissertation zur Erlangung des Doktorgrades der Naturwissenschaftlichen Fachbereiche (Fachbereich Mathematik) der Justus-Liebig-Universität Gießen

Institut:
Institut für Informatik, Justus-Liebig-Universität Gießen

Erscheinungsjahr:
1999

Abstract:
Die vorliegende Arbeit beschäftigt sich mit der Entwicklung und Optimierung verteilter Algorithmen zu Problemen aus der Zahlentheorie. Speziell werden vier Probleme behandelt. Zur Vorbereitung auf die Bewertung der jeweils vorzustellenden Algorithmen wird in Kapitel 1 zunächst ein neues Berechnungsmodell entwickelt, das bestehende Modelle um in der Praxis relevante Eigenschaften erweitert und die formale Grundlage sämtlicher Verfahren darstellt. Berücksichtigt werden dabei sowohl Unterschiede in den Komplexitäten verschiedener Operationen als auch Kosten für Speicherzugriffe. Beides hat in der Praxis entscheidenden Einfluß auf die Gesamtkomplexität der Implementierungen von Algorithmen. Der Grundaufbau des Modells wird zunächst formal definiert, den Instruktionen der Modellmaschine dann Kosten zugeordnet.

Es folgt die Einführung einer Sprache zur Algorithmenbeschreibung. Diese wird schließlich zum Zwecke der Analyse der folgenden Verfahren durch Angabe eines übersetzers in Modellmaschinen-Instruktionen auf das Berechnungsmodell zurückgeführt. Sämtliche vorzustellenden Algorithmen werden anhand der Beschreibungssprache erläutert und mit dem vorher geschaffenen Komplexitätsmaß bewertet. Diese Vorgehensweise läßt eine wesentlich realistischere Bewertung der Komplexitäten zu als es in herkömmlichen Modellen möglich gewesen wäre. Eine "Tauglichkeitsuntersuchung" des entstandenen Komplexitätsmaßes für Programme über dieser Sprache wird im Zusammenhang des nachfolgenden Kapitels durchgeführt.

Kapitel 2 beschäftigt sich mit Primzahl-Sieben, also Algorithmen zur Trennung zerlegbarer Zahlen von Primzahlen eines gegebenen Intervalls. Die Basis stellt dabei das über 2000 Jahre alte Sieb des Eratosthenes dar. Zunächst werden daran einige einfache Verbesserungen vorgenommen. An der Analyse der daraus resultierenden Verfahren zeigt sich, daß selbst feine Unterschiede durch das Komplexitätsmaß der Beschreibungssprache erfaßt werden können. In einem nächsten Schritt findet dann zur Vorbereitung auf eine spätere Verteilung die Segmentierung des Basissiebes statt. Der Begriff der Segmentierung, der im Bereich der Primzahlsiebe eine gewisse Tradition hat, wird in dieser Arbeit übernommen. Er ist zum einen als theoretische Vorstufe zu einer praktischen Verteilung zu verstehen und soll zum anderen vom Begriff der Partitionierung abgrenzen, unter der man häufig eine disjunkte Zerlegung versteht, die hier nicht immer gemeint sein muß.

Ausgehend von einer ersten segmentierten Version werden schrittweise Verbesserungen entwickelt, die schließlich in einem hochoptimierten Verfahren münden. Es wird gezeigt, daß dieses trotz seiner asymptotisch schlechteren Laufzeit unter realistischen Bedingungen andere Algorithmen übertrifft. Eine Implementierung des resultierenden Primzahlsiebes wird beschrieben. Dabei wurde auf möglichst weitreichende Parametrisierbarkeit geachtet, die sich in späteren Anwendungen zum Teil erheblich auswirkt.

In Kapitel 3 wird eine (Teil-) Verifikation der inzwischen über 250 Jahre alten Goldbachschen Vermutung vorgenommen. Dabei handelt es sich um die Frage, ob sich jede gerade Zahl größer oder gleich 4 als Summe zweier Primzahlen darstellen läßt. Trotz der Einfachheit ihrer Formulierung zählt man einen möglichen Beweis der Goldbachschen Vermutung zu den schwierigsten Problemen der gesamten Mathematik überhaupt.

Es werden zunächst zwei Methoden zur Verifikation beschrieben sowie deren Vor- und Nachteile aufgezeigt. Aus diesen Überlegungen folgt die Auswahl eines der beiden Verfahren. Laufzeitkritische Punkte konnten durch mehrere Optimierungen entscheidend verbessert werden. Der resultierende Algorithmus wurde implementiert und schließlich verteilt. Das Ergebnis der Rechnung - die Verifikation bis 4x10¹⁴ - stellt eine Ausdehnung des bisher bestätigten Bereichs auf das Vierfache dar.

Eine Erweiterung des Goldbachschen Problems ist die Frage nach der Anzahl der Zerlegungen gerader Zahlen als Summe zweier Primzahlen. Das Problem der Bestimmung dieser Anzahl läßt sich durch einen sequentiellen Algorithmus eigentlich sehr einfach lösen. Allerdings stößt das Verfahren in der Praxis schnell an seine Grenzen, die vor allem aus dem Mangel an zur Verfügung stehendem Hauptspeicher resultieren. Es wird zunächst gezeigt, daß durch eine Segmentierung des Basisverfahrens ein Minimum an Speicher genügt. Allerdings führt die beschriebene Vorgehensweise zunächst zu einer deutlichen Erhöhung der Zeitkomplexität, die jedoch praktisch durch die sich automatisch ergebende Verteilbarkeit aufgefangen werden kann. Das Ergebnis der verteilten Berechnung - der Bestimmung der Anzahlen der Partitionen aller geraden Zahlen bis 5x10⁸ - wird schließlich verschiedenen historischen Vermutungen über das Wachstum der Anzahl der Partitionen gegenübergestellt.

Kapitel 5 stellt ein Verfahren zur verteilten Suche nach modulo p verschwindenden Fermat-Quotienten zur Basis a für prime a und p vor. Die dazu äquivalente Frage der Lösbarkeit der Kongruenz a^p-1 = 1 mod p² wurde erstmals vor etwa 170 Jahren von N. Abel aufgeworfen. Sie steht in engem Zusammenhang mit dem (inzwischen von A. Wiles bewiesenen) letzten Satz von Fermat . Über die Lösungen der Kongruenz oder ihrer Struktur ist relativ wenig bekannt. Es wird zunächst ein einfacher Algorithmus beschrieben, der jedoch in der Praxis entscheidende Nachteile aufweist. Selbst nach der Ersetzung einiger problematischer Stellen verbleiben praktische Schwierigkeiten, die nur durch eine recht komplizierte, aber letztendlich erfolgreiche Vorgehensweise behoben werden können.

Das resultierende und schließlich implementierte und verteilte Verfahren zeigt eine praktische Schranke für eine im Berechnungsmodell getroffene Idealisierung auf, die trotz der relativ umständlichen Methode nicht durchbrochen werden mußte. Die getroffene Idealisierung erfährt damit eine weitere Rechtfertigung. Durch eine maschinennahe Implementierung und Verteilung konnten bisherige Berechnungen zum Problem der Fermat-Quotienten um das etwa zwölffache erweitert werden. Die für alle primen a<1000 und p<10¹¹ durchgeführte Rechnung lieferte acht neue Lösungen, darunter eine, die die erste Lösung zur Basis a=929 darstellt.

Abschließend wird eine Softwareimplementierung zur Steuerung verteilter Rechnungen vorgestellt. Dabei werden sowohl vernetzte Systeme mit oder ohne gemeinsamem Speicher unterstützt als auch einzelne Rechner eingebunden, die nur teilweise netzverbunden sind oder auch völlig getrennt arbeiten. Durch die relativ schlanke Struktur und einfache Konfigurierbarkeit ist es prinzipiell möglich, weltweite Rechnerressourcen in eine verteilte Rechnung einzubinden. Netzkommunikationen werden dabei weitestgehend vermieden, um eine Abhängigkeit von zentralen Servern zu vermeiden. Sämtliche Rechnungen wurden unter Verwendung dieser Software auf relativ kleinen Rechnern an unterschiedlichen Standorten durchgeführt.

Sprache:
deutsch

Dateiformat:
PostScript (gzip compressed)

Sachgruppen der DNB:
27 Mathematik, 28 Informatik

Eingabedatum:
10.08.1999

Zurück zum Anfang	Zur "Giessener Elektronischen Bibliothek"
Fragen und Kommentare bitte an: geb@bibsys.uni-giessen.de	Zuletzt geändert am 30.08.1999