Computer Science/Discrete Mathematics Seminar II

This talk gives an introduction on how to quickly solve linear systems where the matrix of the system is the Laplacian matrix of any undirected graph. No prior familiarity with optimization is assumed. In the process, we will cover:

• what positive semidefinite matrices are and why mathematicians say they "behave like nonnegative numbers" (mainly intended as a review)
• the Loewner ordering (standard PSD ordering) on positive semidefinite matrices and how it provides a natural definition of "multiplicative approximation" for them
• Richardson iteration / gradient descent for solving quadratic minimization problems
• preconditioning and why we care about the sparsity of the matrix when trying to solve linear systems quickly
• spectral sparsification of graphs (presented/used as a black box statement)
• the Peng-Spielman algorithm for solving laplacian linear systems in nearly linear time. (Solves a Laplacian linear system with m nonzero entries in m*polylog(m) time. This is only slightly more than the time it takes to write down the system. Compared to the best runtime achievable using fast matrix multiplication algorithms, even if the exponent for matrix multiplication is 2, the Peng-Speilman algorithm is much faster in sparse graphs. Even in dense graphs, it is never slower by more than a polylogarithmic factor.)