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

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.