Mit 42 Ziffern Geschichte schreiben: Wissenschaftler der Universit?t Paderborn und der KU Leuven haben mit der sogenannten neunten Dedekind-Zahl ein jahrzehntealtes Mysterium der Mathematik erschlossen. Nach dem Wert suchen Expert*innen weltweit seit 1991. Zu der exakten Zahlenfolge sind die Paderborner Wissenschaftler mithilfe des dort beheimateten Supercomputers Noctua gelangt. Die Ergebnisse werden im September beim ?International 360直播吧 on Boolean Functions and their Applications (BFA)“ in Norwegen vorgestellt.
Was als Masterarbeits-Projekt von Lennart Van Hirtum, damals Informatikstudent an der KU Leuven und heute wissenschaftlicher Mitarbeiter an der Universit?t Paderborn, gestartet ist, wurde zu einem Riesenerfolg. Die Wissenschaftler reihen sich mit ihrer Arbeit in eine illustre Runde ein: Frühere Zahlen aus der Serie wurden vom Mathematiker Richard Dedekind selbst gefunden, als er das Problem 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 überhaupt m?glich ist, diese Zahl jemals zu errechnen“, so Van Hirtum.
Die vorherige Zahl in der Dedekind-Folge, die 8. Dedekind-Zahl, wurde 1991 mit einer Cray 2, dem damals leistungsf?higsten Supercomputer, gefunden. ?Uns schien es deshalb denkbar, dass es inzwischen m?glich sein sollte, die 9. Zahl auf einem gro?en Supercomputer zu berechnen“, schildert Van Hirtum die Motivation für das ambitionierte Vorhaben, das er anf?nglich gemeinsamen mit den Betreuern seiner Masterarbeit an der KU Leuven umgesetzt hat.
Sandk?rner, Schach und Supercomputer
Der Hauptgegenstand 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 unendlich vielen Dimensionen als ein Spiel mit einem Würfel vorstellen. Man balanciert den Würfel auf einer Ecke und f?rbt dann jede der übrigen Ecken entweder wei? oder rot. Dabei gibt es nur eine Regel: Man darf niemals eine wei?e Ecke oberhalb einer roten platzieren. Dadurch entsteht eine Art vertikaler Rot-Wei?-Schnitt. Das Ziel des Spiels ist es, zu z?hlen, wie viele verschiedene Schnitte es gibt. Deren Anzahl ist das, was als Dedekind-Zahl definiert wird. Auch wenn es nicht so wirkt, die Zahlen werden dabei schnell gigantisch: Die 8. Dedekind-Zahl hat bereits 23 Ziffern.“
Vergleichbar gro?e – aber ungleich leichter zu berechnende – Zahlen sind aus einer Legende zur Erfindung des Schachspiels bekannt. ?Demzufolge soll sich dessen Erfinder zur Belohnung nur einige Reisk?rner auf jedem Feld des Schachbretts vom K?nig gewünscht haben: ein Korn auf dem ersten Feld, zwei K?rner auf dem zweiten, vier auf dem dritten und auf jedem folgenden Feld jeweils doppelt so viele. Der K?nig stellte schnell fest, dass diese Bitte unm?glich zu erfüllen war, denn so viel Reis existiert auf der ganzen Welt nicht. Die Anzahl der Reisk?rner auf dem kompletten Brett h?tte 20 Ziffern – unvorstellbar viel, aber immer noch weniger als D(8). Wenn man sich diese Gr??enordnungen bewusst macht, ist offensichtlich, dass sowohl eine effiziente Rechenmethode als auch ein sehr schneller Computer notwendig sein würden, um D(9) zu finden“, so Van Hirtum.
Aus Jahren werden Monate
Zur Berechnung von D(9) verwendeten die Wissenschaftler eine von Masterarbeitsbetreuer Prof. Dr. Patrick De Causmaecker entwickelte Technik, die als P-Koeffizienten-Formel bekannt ist. 360直播吧 bietet eine M?glichkeit, Dedekind-Zahlen nicht durch Z?hlen, sondern durch eine sehr gro?e Summe zu berechnen. Damit kann D(8) in lediglich acht Minuten auf einem normalen Laptop entschlüsselt 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 immer noch viele Jahre dauern, bis die Berechnung abgeschlossen ist“, gibt Van Hirtum zu bedenken. Das Hauptproblem ist, dass die Anzahl der Terme in dieser Formel unglaublich schnell w?chst. ?In unserem Fall konnten wir durch Ausnutzung von Symmetrien in der Formel die Anzahl der Terme auf ?nur' 5,5*10^18 reduzieren – eine enorme Menge. Zum Vergleich: Die Anzahl der Sandk?rner auf der Erde betr?gt etwa 7,5*10^18. Das ist zwar nicht zu verachten, aber für einen modernen Supercomputer sind 5,5*10^18 Operationen durchaus verkraftbar“, so der Informatiker. Das Problem: Die Berechnung dieser Terme auf normalen Prozessoren ist langsam und auch eine Nutzung von GPUs als aktuell schnellste Hardwarebeschleunigertechnologie für viele KI-Anwendungen ist für diesen Algorithmus nicht effizient.
Die L?sung: anwendungsspezifische Hardware, in der hochspezialisierte und parallele Rechenwerke verwendet werden – sogenannte FPGAs (field programmable gate arrays). Van Hirtum entwickelte einen ersten Prototyp für den Hardware-Beschleuniger und begann, sich nach einem Supercomputer umzusehen, der über die notwendigen FPGA-Karten verfügt. Dabei wurde er auf den Noctua 2-Rechner des ?Paderborn Center for Parallel Computing (PC2)“ der Universit?t Paderborn aufmerksam, der über eines der weltweit leistungsf?higsten FPGA-Systeme verfügt.
Prof. Dr. Christian Plessl, Leiter des PC2, erkl?rt: ?Als Lennart Van Hirtum und Patrick De Causmaeker mit uns Kontakt aufgenommen haben, war für uns sofort klar, dass wir dieses Moonshot-Projekt unterstützen wollen. Die L?sung von harten kombinatorischen Problemen mit FPGAs ist ein vielversprechendes Anwendungsfeld und Noctua 2 ist einer der wenigen Supercomputer weltweit, mit denen das Experiment überhaupt durchführbar ist. Die extremen Anforderungen an Zuverl?ssigkeit und Stabilit?t stellen auch eine Herausforderung und Test für unsere Infrastruktur dar. Das FPGA-Fachberatungsteam hat eng mit Lennart zusammengearbeitet und die Anwendung für unsere Umgebung angepasst und optimiert.“
Nach einer mehrj?hrigen Entwicklungszeit lief das Programm rund fünf Monate lang auf dem Supercomputer. Und dann war es soweit: Am 8. M?rz haben die Wissenschaftler die 9. Dedekind-Zahl gefunden: 286386577668298411128469151667598498812366.
Heute, drei Jahre nach dem Start des Dedekind-Projekts, arbeitet Van Hirtum als Stipendiat der NHR-Graduiertenschule am Paderborner Center for Parallel Computing, um in seiner Promotion die n?chste Generation von Hardwarewerkzeugen zu entwickeln. Die NHR (Nationales Hochleistungsrechnen) Graduate School ist die gemeinsame Graduiertenschule der NHR-Zentren.
?ber seinen au?ergew?hnlichen Erfolg berichtet er zusammen mit De Causmaecker am 27. Juni um 14 Uhr in H?rsaal O2 der Universit?t Paderborn. Die interessierte ?ffentlichkeit ist herzlich eigeladen.
