A Fast Distributed Solver for Symmetric Diagonally Dominant Linear Equations

Abstract

In this paper, we propose a fast distributed solver for linear equations given by symmetric diagonally dominant M-Matrices. Our approach is based on a distributed implementation of the parallel solver of Spielman and Peng by considering a specific approximated inverse chain which can be computed efficiently in a distributed fashion. Representing the system of equations by a graph $\mathbb{G}$, the proposed distributed algorithm is capable of attaining $\epsilon$-close solutions (for arbitrary $\epsilon$) in time proportional to $n^3$ (number of nodes in $\mathbb{G}$), $\alpha$ (upper bound on the size of the R-Hop neighborhood), and $\frac{W_{max}}{W_{min}}$ (maximum and minimum weight of edges in $\mathbb{G}$).

References in corpus (1)

• Faster generation of random spanning trees