A Posteriori Error Estimates for Solving Graph Laplacians

In this paper, we study a posteriori error estimators which aid multilevel iterative solvers for linear systems with graph Laplacians. In earlier works such estimates were computed by solving global optimization problems, which could be computationally expensive. We propose a novel strategy to compute these estimates by constructing a Helmholtz decomposition on the graph based on a spanning tree and the corresponding cycle space. To compute the error estimator, we solve efficiently the linear system on the spanning tree, and then we solve approximately a least-squares problem on the cycle space. As we show, such an estimator has a nearly-linear computational complexity for sparse graphs under certain assumptions. Numerical experiments are presented to demonstrate the efficacy of the proposed method.