Auf Ziffernsuche, Universität Paderborn, 9 Dedekind Zahl entdeckt

Auf Ziffernsuche, Universität Paderborn, 9 Dedekind Zahl entdeckt: Wissenschaftler der Universitäten Paderborn und Leuven lösen langbekanntes Problem der Mathematik

Paderborn, 26. Juni 2023

Mit 42 Ziffern Geschichte schreiben: Wissenschaftler der Universität Paderborn und der KU Leuven haben mit der 9. sogenannten 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 Workshop 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 einem #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: 1 Korn auf dem ersten Feld, 2 Körner auf dem 2., 4 auf dem 3. 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. Sie 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 8 Minuten auf einem normalen Laptop entschlüsselt werden. Aber: »Was für D (8) 8 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 mal 10 hoch 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 mal 10 hoch 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 (PC 2)« 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 5 Monate lang auf dem Supercomputer. Und dann war es soweit: Am 8. März haben die Wissenschaftler die 9. Dedekind Zahl gefunden: 286.386.577.668.298.411.128.469.151.667.598.498.812.366.

Heute, 3 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 2023 um 14 Uhr in Hörsaal O 2 der Universität Paderborn. Die interessierte Öffentlichkeit ist herzlich eigeladen. Mehr …