Abstract
As illustrated by several other talks in this boot camp, the combinatorial properties of a graph are deeply connected to the linear algebraic properties of its Laplacian, and the ability to solve linear systems (and other algebraic problems) in graph Laplacians provides a powerful tool for probing the structure of a graph. As such, 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 Laplacian systems has been an active area of research since the 1960s. This has culminated in recent algorithms that exploit the interplay between the combinatorial structure of a graph and the linear algebraic structure of its Laplacian to solve these systems in nearly-linear time. In this series of lectures, I will discuss the main ideas behind two such algorithms. I will begin by briefly describing classical iterative methods for general linear systems and the problems they encounter when applied to Laplacians. I will then introduce the techniques from spectral and combinatorial graph theory, graph algorithms, and iterative methods that allow us to overcome these problems and solve Laplacian systems in nearly-linear time.
The lectures will be self-contained and will not assume prior background in computational linear algebra.
The first session of this talk will take place on Wednesday, August 27 from 3:30 pm – 4:30 pm; the second session of this talk will take place on Thursday, August 28 from 10:00 am – 11:00 am.