ausblenden:
Schlagwörter:
Computer Science, Discrete Mathematics, cs.DM,Computer Science, Data Structures and Algorithms, cs.DS
Zusammenfassung:
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\geq N\sqrt{\phi_{w}/\delta}$
distinct Binomial distributions $B(\cdot,N)$ that $\delta$-approximates a
\emph{discretized} p.d.f. $\hat{w}(i/N)\triangleq
w(i/N)/[\sum_{\ell=0}^{N}w(\ell/N)]$ for all $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 $\epsilon\in(0,1)$,
outputs in $\hat{O}(\epsilon^{-2}m + \epsilon^{-4}nT)$ time a spectral
sparsifier $D-\hat{M}_{N} \approx_{\epsilon} D-D\sum_{i=0}^{N}\beta_{i}(D^{-1}
M)^i$ of a matrix-polynomial, where $\hat{O}(\cdot)$ notation hides
$\mathrm{poly}(\log n,\log N)$ factors. This improves the Cheng et
al.'s\cite{CCLPT15} algorithm whose run time is $\hat{O}(\epsilon^{-2} m N^2 +
NT)$.
Furthermore, our algorithm is parallelizable and runs in work
$\hat{O}(\epsilon^{-2}m + \epsilon^{-4}nT)$ and depth $O(\log
N\cdot\mathrm{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\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. $\hat{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\cite{PS14} parallel SDD solver.
