 |
Center for Nonlinear Studies |
We consider design of fast and robust iterative algorithm for distributed linear computation based on classical linear update method. The design of such an algorithm involves finding transition matrix P of a Markov chain on network graph $G$ with fast mixing time and small size (number of non-zero entries in P). We present a novel method, which we call {\em pseudo-lifting} to construct such a desirable P starting from a given matrix Q (say, that obtained by Metropolis-Hastings rule). Under thus constructed P, the total distributed operations for linear computation is $\tilde O\left((|E|+Dn)D\right)$, where $D$ is the diameter of $G$, and $n$ is the number of nodes. This construction works for any graph and does not utilize any structural graph properties. Next, we present a {\em hierarchical} construction that cleverly utilizes the geometry of the graph to obtain P with much smaller computation cost. Specifically, for graphs with doubling dimension $\rho$, it takes $\tilde O\lf(D^2n^{1-\frac{1}{1+\rho}}\rf)$ total operations.
Our results imply an explicit construction of a Markov chain with fastest possible mixing time, of order of the graph diameter, on any graph using the {\em pseudo-lifting} -- this should be of interest in its own right.