UC Santa Barbara

Solving Laplacian linear systems is an important task in a variety of practical and theoretical applications. Laplacians of structured graphs, such as two and three dimensional meshes, have long been important in finite element analysis and image processing. More recently, solving linear systems on the Laplacians of large graphs without mesh-like structure has emerged as an important computational task in network analysis. A number of theoretical solvers with good asymptotic complexity have been proposed over the past couple decades, but these ideas have not made their way into practical solvers. Nor is it clear that a class of challenging problems exist which would benefit from asymptotically fast solvers. Yet it seems that one of the following should be true: either existing solvers have tighter Big-O bounds than currently believed, or there are some problems where recent asymptotically fast (but theoretical) algorithms should be useful.

This work considers the latter possibility; we aim to bridge the gap between theoretical and practical Laplacian algorithms by experimenting with Laplacian solvers and by searching for difficult test problems. We examine the performance of existing algorithms for solving Laplacian linear systems and identify the strengths and weaknesses of different methods on different test problems. We perform an extensive evaluation of the KOSZ solver, one of the recently proposed Õ(m) Laplacian algorithms. We test various extensions of KOSZ which we propose to try and improve its performance in practice. We introduce heavy path graphs, a novel class of graphs for experimenting with Laplacian solvers.

To challenge existing solver implementations, we propose the use of genetic algorithms to create difficult test graphs for existing solvers. At the same time, these algorithms could be used to find graphs with good performance for recently proposed solvers. Searching for graphs which satisfy both objectives could be instrumental towards bridging the theory-practice gap of Laplacian solvers. We demonstrate the successful evolution of graphs which are difficult for conjugate gradient with diagonal scaling, while relatively simple for KOSZ. Such graph evolution techniques could be useful for finding graphs with a variety of combinatorial properties.