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.

Trilinos

Trilinos is a project out of Sandia National Labs for developing robust parallel algorithms and implementing them with general purpose software. The focus of the project is enabling technologies for large-scale scientific problems as to encourage further research in the field of parallel, robust, large-scale algorithms. In recognition of existing software for numerical computation, the developers at Trilinos make use of established packages such as LAPACK (for solving systems of simultaneous linear equations), and provides interfaces for Aztec (a parallel solver for sparse linear systems), SuperLU (high performance LU factorization for solving linear systems), Mumps, and Umfpack among others. Currently, Trilinos provides robust parallel numerical algorithms for automatic differentiation, partitioning, preconditioning, and solving linear and nonlinear systems to name a few. The beauty of having a team of algorithmists behind the project is the emphasis on enabling further algorithmic research by building tools for developing tools.

Zoltan

Erik Boman has contributed important work in the area of the preconditioners for linear systems and the support theory for preconditioners. Zoltan, one of his projects, is a toolkit also from Sandia National Labs comprised of combinatorial algorithms for parallel or unstructured applications. It uses dynamic load balancing and partitioning algorithms for parallelizing the computation of applications whose work loads change over the course of the computation. To deal with the problem of dynamic partitioning, a suite of partitioning algorithms is included in the Zoltan toolkit. In particular, it makes use of geometric algorithms (group together objects that are physically close), graph algorithms (minimize a cut dividing groups of objects), and hypergraph algorithms (minimize communication costs between groups of objects) for load balancing partitioning. Another important function Zoltan provides is for graph coloring and graph ordering, which in turn can be used for parallel preconditioners and linear solvers.

Sangria

Sangria is another project focused on developing and implementing parallel geometric and numerical algorithms. Housed at Carnegie Mellon, the software uses parallel algorithms for simulating complex flows with dynamic interfaces that achieves good accuracy.

MatlabBGL

MatlabBGL is a Matlab package written by David Gleich, designed to work with sparse graphs on hundreds of thousands of nodes. The library includes common graph algorithms such as computing shortest paths (Dijkstra, Bellman-Ford, Floyd-Warshall), finding an minimum spanning tree (Kruskal, Prim), depth-first search, breadth-first search, and max flow – all optimized for efficiency on large graphs. One of the most useful features of MatlabBGL is the visitor feature for monitoring an algorithm, implemented from the Boost Graph Library. Visitors output all the steps taken by the algorithm, and dissecting the output is useful for optimization. A nice illustration of this feature with Dijkstra’s algorithm in the documentation tells us how a graph is explored, vertex by vertex.

SVR Meshing

Benoît Hudson’s PhD work was on sparse mesh refinement, and SVR (for Sparse Voronoi Refinement) is the implementation of his algorithm for Delaunay refinement. SVR is a provably fast algorithm for producing small meshes, which is useful for when remeshing occurs during simulation due to domain change or refinement.

CMG + SpA

SpA is a Matlab program for computing the effective resistances in an electrical network and is an implementation of the Spielman-Srivastrava. As this requires solving linear systems, it uses Combinatorial Multigrid (CMG), a Matlab-based solver for linear systems in symmetric diagonally-dominant matrices written by Yiannis Koutis.

This is by no means a comprehensive list, I encourage you include more useful software in the comments.