Spectral Graph Theory Lecture 19 Fast Laplacian Solvers by Sparsification

These notes are not necessarily an accurate representation of what happened in class. The notes written before class say what I think I should say. I sometimes edit the notes after class to make them way what I wish I had said. There may be small mistakes, so I recommend that you check any mathematically precise statement before using it in your own work. These notes were last revised on November 9, 2015. 19.1 Overview We will see how sparsification allows us to solve systems of linear equations in Laplacian matrices and their sub-matrices in nearly linear time. By “nearly-linear”, I mean timeO(m logc(nκ−1) log −1) for systems with m nonzero entries, n dimensions, condition number κ. and accuracy . This algorithm comes from [PS14]. 19.2 Today’s notion of approximation In today’s lecture, I will find it convenient to define matrix approximations slightly differently from previous lectures. Today, I define A ≈ B to mean e−A 4 B 4 eA. Note that this relation is symmetric in A and B, and that for small e ≈ 1 + . The advantage of this definition is that A ≈α B and B ≈β C implies A ≈α+β C. 19.3 The Idea I begin by describing the idea behind the algorithm. This idea won’t quite work. But, we will see how to turn it into one that does