A Multigrid Solver for Graph Laplacian Linear Systems on Power-Law Graphs
Knepley, Matthew G
Master of Arts
The Laplacian matrix, L, of a graph, G, contains degree and edge information of a given network. Solving a Laplacian linear system Lx = b provides information about flow through the network, and in specific cases, how that information orders the nodes in the network. I propose a novel way to solve this linear system by first partitioning G into its maximum locally-connected subgraph and a small subgraph of the remaining so-called "teleportation" edges. I then apply optimal multigrid solves to the locally-connected subgraph, and linear algebra and a solve on the teleportation subgraph to solve the original linear system. I show results for this method on real-world graphs from the biological systems of the C. Elegans worm, Facebook friend networks, and the power grid of the Western United States.