TECH
How randomness tames vast network problems
Networks are everywhere. They connect computers across the internet, carry electricity through power grids and represent transport routes for moving people and goods. Yet many problems that appear to have nothing to do with networks can also be represented and solved as networks. Examples include matching passengers with drivers in a ride-hailing app or distributing computing tasks across servers.
The research group of theoretical computer scientist Rasmus Kyng develops new computational methods for solving equations that describe very large networks. The challenge lies in the scale of these networks.
Once a network contains millions or even billions of connections, solving the equations becomes particularly demanding. Methods that work well on small networks often require so much time and memory that they become impractical at this scale.
Kyng's work combines two activities: developing exceptionally fast algorithms, the mathematical procedures that guide a computation, and turning these algorithms into practical software.
Recently, Kyng, his former student Yuan Gao and his one-time doctoral supervisor Daniel Spielman presented a new solver for Laplacian equations in the SIAM Journal on Scientific Computing. A solver is a computer program that automatically solves mathematical equations.
The prototype of the new solver already proved both reliable and substantially faster than existing software across a wide range of test cases. "The results show that methods developed in theoretical computer science can become practical tools for solving very large network problems," says Kyng.
A two-stage research process...The story of Laplacian solvers provides a particularly clear example of how a theoretical proof can eventually become software for supercomputers. Kyng's research typically proceeds in two stages: mathematical theory and practical implementation.
The first stage centers on fundamental mathematical questions such as this: Can one prove that a problem can be solved by an algorithm whose computational cost grows only moderately as the problem becomes larger?
This question matters because the computational cost of many algorithms rises sharply as problems grow. If a network becomes 10 times larger, one would ideally want the required computation to increase by roughly the same factor. In practice, however, the computational effort often increases much more rapidly than the size of the problem.
A major focus of Kyng's research is the development of algorithms with nearly linear running times. In such algorithms, the computational effort grows almost in step with the size of the problem. In recognition of his scientific work on highly efficient algorithms, Kyng received the 2025 ETH Zurich Latsis Prize.
Alongside the goal of making computational efforts grow as close as possible to the size of the problem itself, another central question guides his work: What information can a computation ignore without losing accuracy?
The mathematical question and its proof are only the beginning. A second stage focuses on turning theoretical insights into practical software that works reliably on real computers. This stage is often challenging: It requires retaining the core mechanisms that create the speed-up, shedding the rest of the theoretical machinery and making those mechanisms work on a real computer.
But is it worth spending years proving that an algorithm is efficient if it initially exists only on paper? "The history of Laplacian solvers provides a compelling answer," says Kyng. "It shows how theoretical insights push the boundaries of what is possible and how they gradually evolve into usable software."
The long path from proof to supercomputer...Back in 2004, computer scientists Daniel Spielman and Shang-Hua Teng proved mathematically that Laplacian equations could be solved in nearly linear time. The result marked a major breakthrough. Yet their approach relied on highly complex mathematical constructions and was not well suited for practical use.
Following this theoretical breakthrough, Kyng and Sushant Sachdeva introduced a much simpler approach in 2016, called Approximate Cholesky. The latest work by Gao, Kyng and Spielman now makes this approach work well in practice.
To build the software prototype, the researchers relaxed some of the very strict theoretical requirements of the 2016 method. The result was a significant increase in speed. In experiments, the software ran about five times faster while remaining reliable across a broad range of Laplacian equations, including problems on which existing software fails.
The work is not finished, however. In the open-source project apxchol, Kyng and his doctoral student Yves Baumann are developing the method into robust software for scientific computing on supercomputers.
Left: When a node is removed, many new connections appear between neighbouring nodes. This makes computations increasingly demanding. Right: Approximate Cholesky considers only a small random sample of these connections. As a result, computations can be significantly accelerated without materially reducing the quality of the results. Credit: Conceptual illustration based on work by Kyng, Sachdeva and collaborators
Pushing beyond existing limits...Why are computations involving Laplacian equations so demanding in the first place?
The researchers build on a technique known as Cholesky elimination. It simplifies a network step by step by removing individual nodes. However, every time a node is removed, new connections appear between the remaining nodes. As a result, the computations become increasingly demanding, requiring ever more computation time and memory.
For small networks, this additional effort is usually manageable. For very large networks, however, it can grow so much that the computations become difficult to carry out in practice.
The Approximate Cholesky method developed by Kyng follows a different strategy. Instead of taking all newly created connections into account, it considers only a small, carefully selected random sample of them. These few connections are sufficient to obtain almost the same results as the full network. As a consequence, computations become much faster without significantly reducing accuracy.
Any remaining errors can then be corrected iteratively. The solution is repeatedly checked and refined until the desired level of accuracy is reached.
The new method is therefore faster than previous approaches while remaining highly reliable across many different test cases. The solver was even able to handle problems on which existing programs failed.
Ultimately, the work demonstrates how a mathematical idea can become a practical tool, capable of solving network problems that were once beyond reach.
The strategic use of randomness allows for solving complex problems in massive networks by drastically reducing computational effort without sacrificing result accuracy. Recently, computer scientists led by Rasmus Kyng at ETH Zurich transformed theoretical concepts into practical software capable of analyzing large networks in near-linear time.
The challenge of traditional networks:
Data explosion: Conventional methods lose speed and require massive amounts of memory when handling immense networks.
Connection buildup: When a network node is removed during standard mathematical calculations (based on so-called Laplacian equations), countless new connections emerge between neighboring nodes, making the process heavy and slow.
The solution: Approximate Cholesky and randomness:
Smart sampling: Instead of recording and processing every newly generated connection, Kyng's algorithm selects only a small, carefully designed random sample of these connections.
Maintaining accuracy: This fraction of connections is statistically sufficient to yield a result virtually identical to what would be generated by analyzing the entire network.
Iterative correction: Any discrepancies or residual errors are repeatedly refined and corrected until the desired level of precision is achieved.
Practical impact and speed:
Five times faster: In real-world experiments, the software prototype ran about five times faster than traditional competitors.
Solving failures: The new system demonstrated high reliability, successfully solving complex problems where previous software simply crashed or failed.
Open source: The breakthrough is being integrated into the open-source software *apxchol*, aiming to accelerate large-scale scientific simulations on supercomputers.
Provided by ETH Zurich
