Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O(m1.31)

Title: Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time O(m1.31)

Research Question: How can we solve sparse, symmetric, diagonally-dominant linear systems more efficiently?

Methodology: The authors developed a linear-system solver that takes an n-by-nsymmetric positive semi-definite, diagonally dominant matrix A with m non-zero entries and an n-vector b, and produces a vector ˜ x with relative distance ǫ of the solution to Ax=b in time O(m1.31log(nκf(A)/ǫ)O(1)). They extended Vaidya's techniques for constructing and analyzing combinatorial preconditioners.

Results: The key contribution of their work is an extension of Vaidya's techniques for constructing and analyzing combinatorial preconditioners. If the graph of A has genus m2θ or does not have a Kmθ minor, the exponent of m can be improved to the minimum of 1 + 5θ and (9/8)(1 + θ). They showed that their algorithm can solve certain PSDDD linear systems in time O((dn)1.2log(κf(A)/ǫ)).

Implications: This research has significant implications for the field of scientific computing and optimization. It provides a more efficient method for solving certain types of linear systems, which are commonly encountered in areas such as elliptic differential equations, resistive networks, and network optimization problems. The new algorithm can solve these systems faster than previous methods, making it a valuable tool for researchers and practitioners in these fields.

Link to Article: https://arxiv.org/abs/0310036v2 Authors: arXiv ID: 0310036v2