Solving Graph Laplacian Systems Through Recursive Bisections and Two-Grid Preconditioning

Ponce, Colin¹  Vassilevski, Panayot S.² 

[1] Cornell Univ., Ithaca, NY (United States);Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)

关键词: graph Laplacian;    recursive bisection;    support graph preconditioners;    two-grid methods;   

DOI  :  10.2172/1240975
RP-ID  :  LLNL--TR-683260
PID  :  OSTI ID: 1240975

学科分类：数学（综合）

美国|英语

来源: SciTech Connect

【 摘 要 】

We present a parallelizable direct method for computing the solution to graph Laplacian-based linear systems derived from graphs that can be hierarchically bipartitioned with small edge cuts. For a graph of size n with constant-size edge cuts, our method decomposes a graph Laplacian in time O(n log n), and then uses that decomposition to perform a linear solve in time O(n log n). We then use the developed technique to design a preconditioner for graph Laplacians that do not have this property. Finally, we augment this preconditioner with a two-grid method that accounts for much of the preconditioner's weaknesses. We present an analysis of this method, as well as a general theorem for the condition number of a general class of two-grid support graph-based preconditioners. Numerical experiments illustrate the performance of the studied methods.