Mit 42 Ziffern Geschichte geschrieben: Wissenschaftler der Universität Paderborn und der KU Leuven haben mit der sogenannten neunten Dedekind-Zahl ein jahrzehntealtes Rätsel der Mathematik gelüftet.
Experten auf der ganzen Welt suchen seit 1991 nach dem Wert. Zur genauen Zahlenfolge gelangten die Paderborner Wissenschaftler mit Hilfe des dort befindlichen Supercomputers Noctua. Die Ergebnisse werden im September auf der vorgestellt Internationaler Workshop zu Booleschen Funktionen und ihren Anwendungen (BFA) in Norwegen.
Was als Masterarbeitsprojekt von Lennart Van Hirtum, damals Informatikstudent an der KU Leuven und heute wissenschaftlicher Mitarbeiter an der Universität Paderborn, begann, hat sich zu einem großen Erfolg entwickelt. Mit ihrer Arbeit reihen sich die Wissenschaftler in eine illustre Runde ein. Frühere Zahlen der Reihe wurden vom Mathematiker Richard Dedekind selbst gefunden, als er das Problem im Jahr 1897 definierte, und später von Größen der frühen Informatik wie Randolph Church und Morgan Ward. „32 Jahre lang war die Berechnung von D(9) eine offene Herausforderung, und es war fraglich, ob es jemals möglich sein würde, diese Zahl zu berechnen“, sagt Van Hirtum.
Die vorherige Zahl in der Dedekind-Reihe, die 8. Dedekind-Zahl, wurde 1991 mit einem Cray 2, dem damals leistungsstärksten Supercomputer, gefunden. „Daher schien es uns denkbar, dass es inzwischen möglich sein sollte, die 9. Zahl auf einem großen Supercomputer zu berechnen“, beschreibt Van Hirtum die Motivation für das ambitionierte Projekt, das er zunächst gemeinsam mit den Betreuern seiner Masterarbeit an realisierte KU Leuven.
Sandkörner, Schach und Supercomputer
Das Hauptthema der Dedekind-Zahlen sind sogenannte monotone Boolesche Funktionen. Van Hirtum erklärt: „Grundsätzlich kann man sich eine monotone Boolesche Funktion in zwei, drei und unendlichen Dimensionen als ein Spiel mit einem n-dimensionalen Würfel vorstellen. Man balanciert den Würfel an einer Ecke und färbt dann jede der verbleibenden Ecken entweder weiß.“ oder Rot. Es gibt nur eine Regel: Sie dürfen niemals eine weiße Ecke über einer roten platzieren. Dadurch entsteht eine Art vertikaler rot-weißer Schnittpunkt.
„Ziel des Spiels ist es, zu zählen, wie viele verschiedene Schnitte es gibt. Ihre Anzahl wird als Dedekind-Zahl bezeichnet. Auch wenn es nicht so aussieht, werden die Zahlen dabei schnell gigantisch: die 8. Dedekind-Zahl.“ hat bereits 23 Ziffern.“
Vergleichsweise große – aber ungleich einfacher zu berechnende – Zahlen sind aus einer Legende über die Erfindung des Schachspiels bekannt. „Dieser Legende zufolge verlangte der Erfinder des Schachspiels vom König als Belohnung nur ein paar Reiskörner auf jedem Feld des Schachbretts: ein Korn auf dem ersten Feld, zwei Körner auf dem zweiten, vier auf dem dritten , und doppelt so viele auf jedem der folgenden Felder. Der König erkannte schnell, dass dieser Wunsch nicht erfüllt werden konnte, da es auf der ganzen Welt nicht so viel Reis gibt.
„Die Anzahl der Reiskörner auf der gesamten Tafel hätte 20 Ziffern – eine unvorstellbare Menge, aber immer noch weniger als D(8). Wenn man sich diese Größenordnungen vor Augen führt, ist es offensichtlich, dass es sich sowohl um eine effiziente Berechnungsmethode als auch um eine sehr schnelle Berechnung handelt „Man braucht einen Computer, um D(9) zu finden“, sagte Van Hirtum.
Meilenstein: Aus Jahren werden Monate
Um D(9) zu berechnen, verwendeten die Wissenschaftler eine vom Betreuer der Masterarbeit Patrick De Causmaecker entwickelte Technik namens P-Koeffizientenformel. Es bietet eine Möglichkeit, Dedekind-Zahlen nicht durch Zählen, sondern anhand einer sehr großen Summe zu berechnen. Dadurch kann D(8) auf einem normalen Laptop in nur acht Minuten dekodiert werden. Aber „Was für D(8) acht Minuten dauert, wird für D(9) zu Hunderttausenden von Jahren. Selbst wenn man einen großen Supercomputer ausschließlich für diese Aufgabe verwenden würde, würde es noch viele Jahre dauern, bis die Berechnung abgeschlossen ist“, so Van Hirtum weist darauf hin.
Das Hauptproblem besteht darin, dass die Anzahl der Terme in dieser Formel unglaublich schnell wächst. „In unserem Fall konnten wir durch die Ausnutzung von Symmetrien in der Formel die Anzahl der Terme auf ‚nur‘ 5,5 x 1018 reduzieren – eine enorme Menge. Im Vergleich dazu beträgt die Anzahl der Sandkörner auf der Erde etwa 7,5 x 1018 „Das ist nicht zu verachten, aber für einen modernen Supercomputer sind 5,5×1018-Operationen durchaus machbar“, sagte der Informatiker.
Das Problem: Die Berechnung dieser Terme auf normalen Prozessoren ist langsam und auch der Einsatz von GPUs als derzeit schnellster Hardware-Beschleunigertechnologie für viele KI-Anwendungen ist für diesen Algorithmus nicht effizient.
Die Lösung: Anwendungsspezifische Hardware mit hochspezialisierten und parallelen Recheneinheiten – sogenannten FPGAs (Field Programmable Gate Arrays). Van Hirtum entwickelte einen ersten Prototypen für den Hardwarebeschleuniger und machte sich auf die Suche nach einem Supercomputer, der über die notwendigen FPGA-Karten verfügte. Dabei wurde er am „Paderborn Center for Parallel Computing (PC2)“ der Universität Paderborn auf den Rechner Noctua 2 aufmerksam, der über eines der weltweit leistungsstärksten FPGA-Systeme verfügt.
Prof. Dr. Christian Plessl, Leiter von PC2, erklärt: „Als Lennart Van Hirtum und Patrick De Causmaeker uns kontaktierten, war uns sofort klar, dass wir dieses Moonshot-Projekt unterstützen wollen. Die Lösung harter kombinatorischer Probleme mit FPGAs ist ein vielversprechendes Feld.“ Der Anwendungsbereich und Noctua 2 ist einer der wenigen Supercomputer weltweit, mit denen das Experiment überhaupt machbar ist. Die extremen Anforderungen an Zuverlässigkeit und Stabilität stellen auch eine Herausforderung und Bewährungsprobe für unsere Infrastruktur dar. Das FPGA-Expertenberatungsteam arbeitete bei der Anpassung und Optimierung eng mit Lennart zusammen die Anwendung für unsere Umwelt.“
Nach mehreren Jahren der Entwicklung lief das Programm etwa fünf Monate lang auf dem Supercomputer. Und dann war es soweit: Am 8. März fanden die Wissenschaftler die 9. Dedekind-Zahl: 286386577668298411128469151667598498812366.
Heute, drei Jahre nach Beginn des Dedekind-Projekts, arbeitet Van Hirtum als Fellow der NHR Graduate School am Paderborn Center for Parallel Computing an der Entwicklung der nächsten Generation von Hardware-Tools in seiner Doktorarbeit. Die NHR (National High Performance Computing) Graduate School ist die gemeinsame Graduiertenschule der NHR-Zentren. Über seinen außergewöhnlichen Erfolg wird er gemeinsam mit Patrick De Causmaecker am 27. Juni um 14 Uhr im Hörsaal O2 der Universität Paderborn berichten.
Bereitgestellt von der Universität Paderborn