Brown University’s ICERM recently hosted a workshop titled “Electrical Flows, Graph Laplacians, and Algorithms,” where top researchers convened to present and discuss their recent progress in spectral graph theory and algorithms. Richard Peng opened up the workshop with an overview talk on efficient solvers for linear systems with graph Laplacians as the coefficient matrix. He presented a thorough history of the topic and set the stage for the variety of technical talks on fast algorithms for graph sparsification, spectral clustering, computing max flow, as well as a variety of other local and approximation algorithms.

His talk (as well as many of the rest) are archived and available thanks to ICERM. I will focus on one highlight – a point that resonated with the conclusion of Richard Peng’s talk – a call for more software implementing these new, fast algorithms. In this light, I’d like to briefly discuss some of the software packages out there for spectral graph theory and the analysis of large graphs being developed by theoreticians active in the area. Continue reading →