# An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials

arXiv: https://arxiv.org/abs/1507.07497 · HTML: https://mlsanity.com/paper/1507.07497/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jul 2015.

## Built on by (most cited first, 1 of 1)

- [Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering](https://mlsanity.com/paper/2207.14589/) (2022)

## Abstract (arXiv)

For "large" class C of continuous probability density functions (p.d.f.), we demonstrate that for every w∈C there is mixture of discrete Binomial distributions (MDBD) with T≥ N√φw/δ distinct Binomial distributions B(·,N) that δ-approximates a discretized p.d.f. widehatw(i/N)triangleq w(i/N)/[sumℓ=0Nw(ℓ/N)] for all i∈[3:N-3], where φw≥maxx∈[0,1]|w(x)|. Also, we give two efficient parallel algorithms to find such MDBD. Moreover, we propose a sequential algorithm that on input MDBD with N=2k for k∈mathbbN+ that induces a discretized p.d.f. β, B=D-M that is either Laplacian or SDDM matrix and parameter ε∈(0,1), outputs in widehatO(ε-2m + ε-4nT) time a spectral sparsifier D-widehatMN ≈ε D-Dsumi=0Nβi(D-1 M)i of a matrix-polynomial, where widehatO(·) notation hides poly(log n,log N) factors. This improves the Cheng et al.'s [CCLPT15] algorithm whose run time is widehatO(ε-2 m N2 + NT). Furthermore, our algorithm is parallelizable and runs in work widehatO(ε-2m + ε-4nT) and depth O(log N·poly(log n)+log T). Our main algorithmic contribution is to propose the first efficient parallel algorithm that on input continuous p.d.f. w∈C, matrix B=D-M as above, outputs a spectral sparsifier of matrix-polynomial whose coefficients approximate component-wise the discretized p.d.f. widehatw. Our results yield the first efficient and parallel algorithm that runs in nearly linear work and poly-logarithmic depth and analyzes the long term behaviour of Markov chains in non-trivial settings. In addition, we strengthen the Spielman and Peng's [PS14] parallel SDD solver.