Fetching the paper…
Reading the bibliography…
We present the first parallel algorithm for solving systems of linear equations in symmetric, diagonally dominant (SDD) matrices that runs in polylogarithmic time and nearly-linear work.
Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners
Pravin M. Vaidya · 1990
Earlier work this paper cites.
Iterative Solution Methods
Owe Axelsson · 1994
Earlier work this paper cites.
Topics in Optimization and Sparse Linear Systems
Anil Joshi · 1997
Earlier work this paper cites.
Efficient approximate solution of sparse linear systems
John Reif · 1998
Earlier work this paper cites.
Random vectors in the isotropic position,
M. Rudelson · 1999
Earlier work this paper cites.
On spanning tree preconditioners
Erik Boman and B. Hendrickson · 2001
Earlier work this paper cites.
A Multigrid Tutorial, 2nd Edition
W. L. Briggs, V. E. Henson, and S. F. McCormick · 2001
Earlier work this paper cites.
Support theory for preconditioning
Erik G. Boman and Bruce Hendrickson · 2003
Earlier work this paper cites.
Iterative Methods for Sparse Linear Systems
Y. Saad · 2003
Earlier work this paper cites.
Learning with local and global consistency
Dengyong Zhou, Olivier Bousquet, Thomas Navin Lal, Jason Weston, and Bernhard Schölkopf · 2003
Earlier work this paper cites.
Semi-supervised learning using Gaussian fields and harmonic functions
Xiaojin Zhu, Zoubin Ghahramani, and John D. Lafferty · 2003
Earlier work this paper cites.
A regularization framework for learning from graph data
Dengyong Zhou and Bernhard Schölkopf · 2004
Earlier work this paper cites.
Support-graph preconditioners
M. Bern, J. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo · 2006
Cited alongside, same era.
A linear work, o ( n 1 / 6 ) o(n^{1/6}) time, parallel algorithm for solving planar Laplacians
Ioannis Koutis and Gary L. Miller · 2007
Cited alongside, same era.
Sampling from large matrices: An approach through geometric functional analysis
Mark Rudelson and Roman Vershynin · 2007
Cited alongside, same era.
Solving elliptic finite element systems in near-linear time with support preconditioners
Erik G. Boman, Bruce Hendrickson, and Stephen A. Vavasis · 2008
Cited alongside, same era.
Faster approximate lossy generalized flow via interior point algorithms
Samuel I. Daitch and Daniel A. Spielman · 2008
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2008
Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing
Ioannis Koutis, Gary L Miller, and David Tolliver · 2011
Later among the works it cites.
Towards an sdp-based approach to spectral methods: A nearly-linear-time algorithm for graph partitioning and decomposition
Lorenzo Orecchia and Nisheeth K Vishnoi · 2011
Later among the works it cites.
Spectral sparsification of graphs
Daniel A. Spielman and Shang-Hua Teng · 2011
Later among the works it cites.
Twice-Ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Later among the works it cites.
Faster approximate multicommodity flow using quadratically coupled flows
Jonathan A. Kelner, Gary L. Miller, and Richard Peng · 2012
Later among the works it cites.
Improved spectral sparsification and numerical algorithms for sdd matrices
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
Daniel A. Spielman and Shang-Hua Teng · 2008
Cited alongside, same era.
Faster generation of random spanning trees
J.A. Kelner and A. Madry · 2009
Cited alongside, same era.
Approaching optimality for solving sdd linear systems
I. Koutis, G.L. Miller, and R. Peng · 2010
Cited alongside, same era.
Near linear-work parallel sdd solvers, low-diameter decomposition, and low-stretch subgraphs
Guy E Blelloch, Anupam Gupta, Ioannis Koutis, Gary L Miller, Richard Peng, and Kanat Tangwongsan · 2011
Cited alongside, same era.
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng · 2011
Cited alongside, same era.
A nearly-mlogn time solver for sdd linear systems
I. Koutis, G.L. Miller, and R. Peng · 2011
Cited alongside, same era.
Alex Levin, Ioannis Koutis, and Richard Peng · 2012
Later among the works it cites.
Approximating the exponential, the lanczos method and an O ~ ( m ) \tilde{O}(m) -time spectral algorithm for balanced separator
Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K. Vishnoi · 2012
Later among the works it cites.
Spectral sparsification in the semi-streaming setting
Jonathan A Kelner and Alex Levin · 2013
Closest in time.
A simple, combinatorial algorithm for solving sdd systems in nearly-linear time
Jonathan A Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013
Closest in time.
Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems
Yin Tat Lee and Aaron Sidford · 2013
Closest in time.
Navigating central path with electrical flows: from flows to matchings, and back
Aleksander Madry · 2013
Closest in time.
A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
Daniel A. Spielman and Shang-Hua Teng · 2013
Closest in time.