Informatiker und Informatikerinnen rund um den ETH-Assistenzprofessor Rasmus Kyng haben ein neues Computerprogramm entwickelt, das grosse Netzwerkprobleme superschnell löst. Grundlage dafür sind Laplace-Gleichungen.

Bisherige Verfahren verlieren bei grossen Netzwerken rasch an Geschwindigkeit und benötigen viel Speicherplatz. Das neue Programm setzt gezielt Zufall ein, um den Rechenaufwand zu begrenzen. Kyngs Gruppe hat nun Erkenntnisse aus ihrer Forschung in die Open-Source-Software Apxchol eingebracht. Sie soll umfangreiche Berechnungen auf Supercomputern beschleunigen.

Netzwerke begegnen uns nicht nur in der IT: Sie leiten auch Strom durch Stromnetze und bilden Verkehrswege für den Transport von Menschen und Gütern ab. Doch viele Probleme, die auf den ersten Blick nichts mit Netzwerken zu tun haben, lassen sich ebenfalls als Netzwerke darstellen und mathematisch lösen: Zum Beispiel die Zuordnung von Fahrgästen zu Fahrerinnen und Fahrern in einer App oder die Verteilung von Rechenaufgaben auf Server.

Viele Netzwerke, etwa Stromnetze oder die Wärmeverteilung in Gebäuden, lassen sich mithilfe der Laplace-Gleichungen mathematisch beschreiben. Diese Gleichungen spielen auch in der Künstlichen Intelligenz eine wichtige Rolle.

Die Forschungsgruppe des theoretischen Informatikers Rasmus Kyng entwickelt neue Rechenverfahren für solche Gleichungen, die sehr grosse Netzwerke beschreiben. Damit können sie gewisse Netzwerkprobleme deutlich schneller lösen. Die Krux liegt in der Grösse dieser Netzwerke.

Bei Netzwerken mit Millionen oder Milliarden von Verbindungen wird die Lösung solcher Gleichungen besonders anspruchsvoll. Verfahren, die auf kleinen Netzwerken problemlos funktionieren, benötigen bei Netzwerken dieser Grösse oft so viel Zeit und Speicherplatz, dass sie praktisch nicht mehr einsetzbar sind.

Die Forschung von Rasmus Kyng umfasst dementsprechend sowohl die Entwicklung besonders schneller Algorithmen, also mathematisch formulierter Rechenverfahren, als auch deren Umsetzung in praktische Software. Erst kürzlich haben Rasmus Kyng, sein ehemaliger Doktorand Yuan Gao und sein früherer Doktorvater Daniel Spielman im 'SIAM Journal on Scientific Computing' einen neuen Solver für Laplace-Gleichungen vorgestellt. Ein Solver ist ein Computerprogramm, das mathematische Gleichungen automatisch löst.

Bereits der Prototyp des neuen Solvers erwies sich in zahlreichen Testfällen als zuverlässig und deutlich schneller als bisherige Software. "Die Ergebnisse zeigen, dass Methoden aus der theoretischen Informatik zu praktischen Werkzeugen für die Lösung sehr grosser Netzwerkprobleme werden können", sagt Kyng.

Wie aus einem theoretischen Beweis eine Software für Supercomputer entsteht, zeigt der Weg der Laplacian-Solver besonders anschaulich. Rasmus Kyngs Forschung durchläuft dabei typischerweise zwei Phasen: die mathematischen Grundlagen und die praktische Umsetzung.

In der ersten Phase geht es um eine grundlegende mathematische Frage wie diese: Gibt es einen Beweis, dass sich ein Problem mit einem Algorithmus lösen lässt, dessen Rechenaufwand auch bei sehr grossen Eingaben nur moderat zunimmt?

Diese Frage ist wichtig, weil der Rechenaufwand vieler Algorithmen in der Praxis mit zunehmender Problemgrösse stark ansteigt. Wird ein Netzwerk zehnmal grösser, sollte die Berechnung möglichst ebenfalls nur etwa zehnmal mehr Aufwand verursachen. In Wirklichkeit jedoch steigt der Rechenaufwand oft sehr viel stärker an als die Problemgrösse.

Ein Schwerpunkt von Kyngs Forschung sind Algorithmen mit nahezu linearer Laufzeit. Bei diesen nimmt der Rechenaufwand nahezu im Gleichschritt mit der Grösse des Problems zu. Für seine Arbeiten an solchen besonders effizienten Algorithmen erhielt Kyng 2025 den Latsis-Preis der ETH Zürich. Mit dem Ziel, den Rechenaufwand möglichst proportional zur Problemgrösse wachsen zu lassen, verbindet sich eine weitere zentrale Frage: Welche Informationen kann eine Berechnung weglassen, ohne an Genauigkeit zu verlieren?

Die mathematische Frage und ihr Beweis sind erst der Anfang. Die zweite Phase dreht sich darum, die theoretischen Erkenntnisse in eine praktische Software zu überführen, die auf realen Computern zuverlässig funktioniert. Diese Phase ist oft anspruchsvoll: Es gilt herauszufinden, was genau die Beschleunigung tatsächlich verursacht, auf unnötige theoretische Konstruktionen zu verzichten und das Verfahren auf realen Computern zum Laufen zu bringen.

Doch lohnt sich der Aufwand, Jahre darauf zu verwenden, die Effizienz eines Algorithmus zu beweisen, wenn dieser zunächst nur auf dem Papier existiert? "Die Geschichte der Laplacian-Solver liefert darauf eine überzeugende Antwort", sagt Rasmus Kyng. "Sie zeigt, wie theoretische Erkenntnisse die Grenzen des Möglichen verschieben und wie daraus Schritt für Schritt eine einsatzfähige Software entsteht."

Bereits 2004 bewiesen die Informatiker Daniel Spielman und Shang-Hua Teng mathematisch, dass sich Laplace-Gleichungen nahezu in linearer Zeit, also superschnell, lösen lassen. Das Ergebnis war ein Meilenstein der Forschung. Ihr Verfahren beruhte jedoch auf sehr komplexen mathematischen Konstruktionen und war für den praktischen Einsatz kaum geeignet.

Nach diesem theoretischen Durchbruch veröffentlichte Kyng 2016 mit Sushant Sachdeva einen deutlich einfacheren Ansatz. Die jüngste Arbeit von Yuan Gao, Rasmus Kyng und Daniel Spielman zeigt nun, dass dieser Ansatz auch in der Praxis gut funktioniert.

Um den Prototyp der Software zu entwickeln, lockerten die Forschenden einige sehr strenge theoretische Anforderungen des Verfahrens von 2016. Dadurch gewann die Software deutlich an Geschwindigkeit. In Experimenten rechnete sie rund fünfmal schneller und erwies sich zugleich bei sehr unterschiedlichen Laplace-Gleichungen als zuverlässig. Darunter waren auch Probleme, an denen bisherige Software scheitert.

Im nächsten Schritt arbeiten Kyng und sein Doktorand Yves Baumann nun im Open-Source-Projekt Apxchol daran, die Methode zu einer robusten Software für den wissenschaftlichen Einsatz auf Supercomputern weiterzuentwickeln.

Warum werden Berechnungen mit Laplace-Gleichungen so aufwendig? Die Forschenden stützen sich auf ein Verfahren namens Cholesky-Elimination. Damit wird ein Netzwerk schrittweise vereinfacht, indem einzelne Knoten entfernt werden. Beim Entfernen von Knoten entstehen jedes Mal neue Verbindungen. Dadurch werden die Berechnungen mit jedem Schritt aufwendiger und benötigen mehr Rechenzeit und Speicherplatz.

Bei kleinen Netzwerken ist dieser zusätzliche Aufwand meist kein Problem. Bei sehr grossen Netzwerken kann er so stark anwachsen, dass die Berechnungen kaum noch praktikabel sind.

Die von Kyng mitentwickelte Methode Approximate Cholesky geht einen anderen Weg. Sie berücksichtigt nur eine kleine, gezielt ausgewählte Zufallsstichprobe der neu entstehenden Verbindungen. Diese wenigen Verbindungen reichen aus, um nahezu dieselben Ergebnisse zu erzielen wie beim vollständigen Netzwerk. Auf diese Weise werden die Berechnungen deutlich schneller, ohne dass die Genauigkeit wesentlich leidet.

Die verbleibenden Abweichungen lassen sich anschliessend schrittweise korrigieren. Dabei wird die Lösung wiederholt überprüft und verbessert, bis die gewünschte Genauigkeit erreicht ist. Die neue Software arbeitet jedenfalls bei grossen Problemen nicht nur schneller als frühere Ansätze, sondern sie erwies sich in vielen Tests auch als zuverlässig.

Damit zeigt die Arbeit, wie aus einer mathematischen Idee ein praktisches Werkzeug werden kann, das selbst Netzwerkprobleme löst, die bislang ausser Reichweite lagen.