Why Laplacian Linear Systems Are Hard, and an Easy Way to Solve Them Quickly

Fast algorithms for solving Laplacian linear systems have found broad applications across both the theory and practice of computer science, playing a foundational role in scientific computing, machine learning, random processes, image processing, network analysis, and computational biology, among others. More recently, they have emerged as a powerful tool in the design of graph algorithms, enabling researchers to break longstanding algorithmic barriers for a wide range of fundamental graph problems.

Finding fast solvers for these systems has been an active area of research since the 1960s, culminating in algorithms that solve them in nearly-linear time. Until recently, the nearly-linear algorithms were quite complex, and developing them required multiple fundamental innovations in spectral and combinatorial graph theory, graph algorithms, and computational linear algebra, which were used to construct and analyze an intricate recursively preconditioned iterative solver.

In recent work with Orecchia and Zhu, we found a new, much simpler combinatorial algorithm that solves Laplacian systems in nearly-linear time while using very little of the machinery that previously appeared necessary for such an algorithm. After constructing a "nice" spanning tree of a graph associated with the system, it just repeatedly applies a simple (non-recursive) update rule implemented using a lightweight data structure. It is numerically stable, has the fastest running time under the standard unit-cost RAM model, and appears amenable to parallel/asynchronous settings.

In this talk, we will survey how the interplay between the combinatorial structure of a graph and the linear algebraic structure of its Laplacian leads to fast solvers. We will discuss the key challenges that a Laplacian solver faces, give a brief overview of previous algorithms, and then describe our algorithm in detail.