论文标题
求解图laplacians的后验错误估计值
A Posteriori Error Estimates for Solving Graph Laplacians
论文作者
论文摘要
在本文中，我们研究了一个后验误差估计器，该误差估计器有助于具有图形laplacian的线性系统的多级迭代求解器。在较早的工作中，通过解决全球优化问题来计算这种估计，这在计算上可能很昂贵。我们提出了一种新的策略，以根据跨越树和相应的循环空间在图上构造helmholtz分解来计算这些估计。为了计算误差估计器，我们在生成树上有效地求解了线性系统，然后在周期空间上解决了大约最小二乘问题。如我们所示，在某些假设下，这种估计器对稀疏图具有近乎线性的计算复杂性。提出了数值实验，以证明该方法的功效。
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.
