Solving Graph Laplacians via Multilevel Sparsifiers

Xiaozhe Hu, Junyuan Lin

We consider effective preconditioners for solving Laplacians of general weighted graphs. Theoretically, spectral sparsifiers (SSs) provide preconditioners of optimal computational…