We consider the solution of linear systems corresponding to the combinatorial graph Laplacian of large unstructured networks. This has emerged as an important computational task in network analysis, along with the corresponding eigenvalue problem. The key when using iterative solvers, such as conjugate gradients, is to find good preconditioners. (This also helps some eigensolvers.)
Most preconditioners were developed for physics-based simulations over meshes. We consider networks that are scale-free with a power-law degree distribution. Our goal is first to study the performance of traditional algebraic preconditioners, and second, to investigate the performance of graph-based preconditioners, such as support-graph preconditioners. Recent work has shown that graph sparsification can produce near-optimal preconditioners. However, these are difficult to compute and little software is available. We show that, perhaps surprisingly, most standard approaches, such as Jacobi, Gauss-Seidel, and incomplete factorizations work quite well on a fixed size problem. Further, a simple spanning tree (forest) preconditioner (MSF) gives slightly better convergence; indicating that more advanced subgraphs may potentially give even better performance. A subtle detail is the diagonal values of the preconditioner. We show that convergence can be improved by a simple modification.
For large problems, parallel computing becomes necessary. We use the Trilinos scientific computing toolkit for our parallel experiments. Many graph algorithms are hard to parallelize so we consider a simpler (more practical) option based on domain decomposition. We use the block Jacobi and additive Schwarz methods, and show that the number of iterations remains almost constant as the number of subdomains increases (up to about 64). We study the impact of graph partitioning, and observed that the graph preconditioner (MSF) is less sensitive to partitioning than the other methods. We conclude that additive Schwarz with a support-graph as a local solver is a robust and competitive iterative solver for graph Laplacians from complex networks.