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.

Many networks, including power grids and the distribution of heat in buildings, can be described mathematically using so-called Laplacian equations. These equations also play an important role in machine learning and artificial intelligence.

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, Rasmus 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 ten 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 effort 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 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, Rasmus Kyng and Sushant Sachdeva introduced a much simpler approach in 2016, called Approximate Cholesky. The latest work by Yuan Gao, Rasmus Kyng and Daniel Spieman 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, Rasmus Kyng and his doctoral student Yves Baumann are developing the method into robust software for scientific computing on supercomputers.

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.