Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
<|reference_start|>Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems: We present a randomized algorithm that, on input a symmetric, weakly diagonally dominant n-by-n matrix A with m nonzero entries and an n-vector b, produces a y such that $\norm{y - \pinv{A} b}_{A} \leq \epsilon \norm{\pinv{A} b}_{A}$ in expected time $O (m \log^{c}n \log (1/\epsilon)),$ for some constant c. By applying this algorithm inside the inverse power method, we compute approximate Fiedler vectors in a similar amount of time. The algorithm applies subgraph preconditioners in a recursive fashion. These preconditioners improve upon the subgraph preconditioners first introduced by Vaidya (1990).   For any symmetric, weakly diagonally-dominant matrix A with non-positive off-diagonal entries and $k \geq 1$, we construct in time $O (m \log^{c} n)$ a preconditioner B of A with at most $2 (n - 1) + O ((m/k) \log^{39} n)$ nonzero off-diagonal entries such that the finite generalized condition number $\kappa_{f} (A,B)$ is at most k, for some other constant c.   In the special case when the nonzero structure of the matrix is planar the corresponding linear system solver runs in expected time $ O (n \log^{2} n + n \log n \ \log \log n \ \log (1/\epsilon))$.   We hope that our introduction of algorithms of low asymptotic complexity will lead to the development of algorithms that are also fast in practice.<|reference_end|>
@article{spielman2006nearly-linear,
    title={Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric,
  Diagonally Dominant Linear Systems},
    author={Daniel A. Spielman and Shang-Hua Teng},
    journal={arXiv preprint arXiv:cs/0607105},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0607105},
    primaryClass={cs.NA cs.DS}
}