A POSTERIORI ERROR ESTIMATES FOR MULTILEVEL METHODS FOR GRAPH LAPLACIANS

In this paper, we study a posteriori error estimators which aid multilevel iterative solvers for linear systems of graph Laplacians. In earlier works such estimates were computed by solving a perturbed global optimization problem, 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 a linear system efficiently on the spanning tree and then 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.