We present an iterative algorithm for solving a class of Laplacian system of equations in @math iterations, where @math is a measure of nonlinearity, @math is the number of variables, @math is the number of nonzero entries in the graph Laplacian @math , @math is the solution accuracy and @math neglects (non-leading) logarithmic terms. This algorithm is a natural nonlinear extension of the one by of Kelner et. al., which solves a linear Laplacian system of equations in nearly linear time. Unlike the linear case, in the nonlinear case each iteration takes @math time so the total running time is @math . For sparse graphs where @math and fixed @math this nonlinear algorithm is @math which is slightly faster than standard methods for solving linear equations, which require approximately @math time. Our analysis relies on the construction of a nonlinear "energy function" and a nonlinear extension of the duality analysis of Kelner et. al to the nonlinear case without any explicit references to spectral analysis or electrical flows. These new insights and results provide tools for more general extensions to spectral theory and nonlinear applications.
Our algorithm is based on Kelner et. al's algorithm @cite_3 , which dramatically reduces the amount of machinery required. Its origins are clearly implicitly based on the more sophisticated machinery in the earlier papers, such as low-stretch spanning trees (e.g., @cite_6 ) and ultra-sparsifiers (e.g., @cite_10 ), but does not require them directly.
@cite_10 @cite_6 @cite_3
2045107949 2072142932 2951126601
We present algorithms for solving symmetric, diagonally-dominant linear systems to accuracy e in time linear in their number of non-zeros and log (κ f (A) e), where κ f (A) is the condition number of the matrix defining the linear system. Our algorithm applies the preconditioned Chebyshev iteration with preconditioners designed using nearly-linear time algorithms for graph sparsification and graph partitioning. We prove that any graph G=(V,E) with n points and m edges has a spanning tree T such that ∑(u,v)∈ E(G)dT(u,v) = O(m log n log log n). Moreover such a tree can be found in time O(m log n log log n). Our result is obtained using a new pet al-decomposition approach which guarantees that the radius of each cluster in the tree is at most 4 times the radius of the induced subgraph of the cluster in the original graph. In this paper, we present a simple combinatorial algorithm that solves symmetric diagonally dominant (SDD) linear systems in nearly-linear time. It uses very little of the machinery that previously appeared to be necessary for a such an algorithm. It does not require recursive preconditioning, spectral sparsification, or even the Chebyshev Method or Conjugate Gradient. After constructing a "nice" spanning tree of a graph associated with the linear system, the entire algorithm consists of the repeated application of a simple (non-recursive) update rule, which it implements using a lightweight data structure. The algorithm is numerically stable and can be implemented without the increased bit-precision required by previous solvers. As such, the algorithm has the fastest known running time under the standard unit-cost RAM model. We hope that the simplicity of the algorithm and the insights yielded by its analysis will be useful in both theory and practice.