Hu, Xiaozhe; Urschel, John C.; Zikatanov, Ludmil T. On the approximation of Laplacian eigenvalues in graph disaggregation. (English) Zbl 1369.05135 Linear Multilinear Algebra 65, No. 9, 1805-1822 (2017). Summary: Graph disaggregation is a technique used to address the high cost of computation for power law graphs on parallel processors. The few high-degree vertices are broken into multiple small-degree vertices, in order to allow for more efficient computation in parallel. In particular, we consider computations involving the graph Laplacian, which has significant applications, including diffusion mapping and graph partitioning, among others. We prove results regarding the spectral approximation of the Laplacian of the original graph by the Laplacian of the disaggregated graph. In addition, we construct an alternate disaggregation operator whose eigenvalues interlace those of the original Laplacian. Using this alternate operator, we construct a uniform preconditioner for the original graph Laplacian. Cited in 1 Document MSC: 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C85 Graph algorithms (graph-theoretic aspects) 65F15 Numerical computation of eigenvalues and eigenvectors of matrices 65F08 Preconditioners for iterative methods 68R10 Graph theory (including graph drawing) in computer science Keywords:spectral graph theory; graph Laplacian; disaggregation; spectral approximation; preconditioning PDFBibTeX XMLCite \textit{X. Hu} et al., Linear Multilinear Algebra 65, No. 9, 1805--1822 (2017; Zbl 1369.05135) Full Text: DOI arXiv