It has been long time we last blogged, due to Bora’s other professional engagements. There has been many things in between, including the 8th SIAM Workshop on CSC (CSC18), June 6–8, 2018, Bergen, Norway. The best paper of CSC18 by Kevin Deweese and John R. Gilbert, entitled Evolving Difficult Graphs for Laplacian Solvers is our subject.

Kevin is currently a PhD student at the University of California, Santa Barbara, working on provably fast Laplacian solvers. See his web page for a few of his papers with experimental evaluation (most of the similar solvers are hard to implement).

Here is the abstract of the subject paper (Link to paper) by Kevin and John:

We seek to discover Laplacian linear systems that stress the ability of existing Laplacian solver packages to solve them efficiently. We employ a genetic algorithm to explore the problem space of graphs of fixed size and edge density. The goal is to measure the gap between theoretical and existing Laplacian solvers, by trying to find worst case example graphs for existing solvers. These problems may have little use inside any real world application, but they give great insight into solver behavior. We report performance results of our genetic algorithm, and explore the properties of the evolved graphs.

Kevin and John focus on the combinatorial solver by Kelner, Orecchia, Sidford, and Zhu (arXiv link) known as KOSZ on the provably fast solver side, and PCG with a Jacobi preconditioner on the traditional side. The genetic algorithms by Kevin and John create populations of graphs by starting with an initial population. Then, a Laplacian solver is run on all graphs and those which required the most work to solve are selected as parents. A random vertex is swapped between the selected parents to yield new individuals. Random edge mutations of the form edge removal and replacement are performed. The techniques are versatile: they are used for creating hard instances for KOSZ and PCG; they are also used to create instances in which the performance of KOSZ with respect to that of PCG varies. On a reported instance, KOSZ outperforms PCG by a factor of 2, and on another one PCG outperforms KOSZ by a factor of 140! In all experiments, the performance is measured in terms of the number of arithmetic operations. Future work includes combining different instances to yield larger problems which stress both solvers to understand our abilities (beware solvers!).