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

For “large” class $\mathcal{C}$ of continuous probability density functions (p.d.f.), we demonstrate that for every $w\in \mathcal{C}$ there is mixture of discrete Binomial distributions (MDBD) with $T\ge N\sqrt{{\varphi }_w\mathrm{/}\delta }$ distinct Binomial distributions $B(\cdot ,N)$ that $\delta$-approximates a discretized p.d.f. $\widehat{w}(i/N)\triangleq w(i/N)/[\sum_{\ell=0}^{N}w(\ell/N)]$forall$i\in[3:N-3]$,where$\phi_{w}\geq\max_{x\in[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=2^k$ for $k\in {\mathbb{N}}_{+}$ that induces a discretized p.d.f. $\beta$, $B=D-M$ that is either Laplacian or SDDM matrix and parameter $ϵ\in (0,1)$, outputs in $\widehat{O}({ϵ}^{-2}m+{ϵ}^{-4}nT)$ time a spectral sparsifier $D-\widehat{M}{N} \approx{\epsilon} D-D\sum_{i=0}^{N}\beta_{i}(D^{-1} M)^i$ofamatrix-polynomial,where$\widehat{O}(\cdot)$notationhides$$\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}$(\log n,\log N)$ factors. This improves the Cheng et al.'s [CCLPT15] algorithm whose run time is $\widehat{O}({ϵ}^{-2}m{N}^2+NT)$. Furthermore, our algorithm is parallelizable and runs in work $\widehat{O}({ϵ}^{-2}m+{ϵ}^{-4}nT)$ and depth $O(\log N\cdot$\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}$(\log n)+\log T)$. Our main algorithmic contribution is to propose the first efficient parallel algorithm that on input continuous p.d.f. $w\in \mathcal{C}$, matrix $B=D-M$ as above, outputs a spectral sparsifier of matrix-polynomial whose coefficients approximate component-wise the discretized p.d.f. $\widehat{w}$. 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.