Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

摘要: We present a randomized algorithm that on input symmetric, weakly diagonally dominant $n$-by-$n$ matrix $A$ with $m$ nonzero entries and an $n$-vector $b$ produces ${\tilde{x}} $ such $\|{\tilde{x}} - A^{\dagger} {b} \|_{A} \leq \epsilon \|A^{\dagger} {b}\|_{A}$ in expected time $O (m \log^{c}n \log (1/\epsilon))$ for some constant $c$. By applying this inside the inverse power method, we compute approximate Fiedler vectors similar amount of time. The applies subgraph preconditioners recursive fashion. These improve upon first introduced by Vaidya 1990. For any nonpositive off-diagonal $k \geq 1$, construct \log^{c} n)$ preconditioner $B$ at most $2 (n 1) + O ((m/k) \log^{39} finite generalized condition number $\kappa_{f} (A,B)$ is $k$, other I...