Fetching the paper…
Reading the bibliography…
We show that Laplacian and symmetric diagonally dominant (SDD) matrices can be well approximated by linear-sized sparse Cholesky factorizations.
On the difference between two neighbouring prime numbers
Nikolai Tchudakoff · 1936
Earlier work this paper cites.
The speed of convergence of one iterative process
Radii Petrovich Fedorenko · 1964
Earlier work this paper cites.
Multi-level adaptive solutions to boundary-value problems
Achi Brandt · 1977
Earlier work this paper cites.
An iterative solution method for linear systems of which the coefficient matrix is a symmetric m m -matrix
J. A. Meijerink and H. A. van der Vorst · 1977
Earlier work this paper cites.
On multigrid convergence in the indefinite case
RA Nicolaides · 1978
Earlier work this paper cites.
Multi-grid convergence theory
Wolfgang Hackbusch · 1982
Earlier work this paper cites.
Multi-grid methods and applications
Wolfgang Hackbusch · 1985
Earlier work this paper cites.
Ramanujan graphs
A. Lubotzky, R. Phillips, and P. Sarnak · 1988
Earlier work this paper cites.
Explicit group theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
G. A. Margulis · 1988
Earlier work this paper cites.
Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners
Pravin M. Vaidya · 1990
Earlier work this paper cites.
An optimal randomised logarithmic time connectivity algorithm for the erew pram
Shay Halperin and Uri Zwick · 1996
Earlier work this paper cites.
Semi-supervised learning using gaussian fields and harmonic functions
X. Zhu, Z. Ghahramani, and J. D. Lafferty · 2003
Earlier work this paper cites.
Support-graph preconditioners
M. Bern, J. Gilbert, B. Hendrickson, N. Nguyen, and S. Toledo · 2006
Earlier work this paper cites.
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.
Extensions and limits to vertex sparsification
Frank Thomson Leighton and Ankur Moitra · 2010
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.
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
Cited alongside, same era.
A new approach to computing maximum flows using electrical flows
Yin Tat Lee, Satish Rao, and Nikhil Srivastava · 2013
Later among the works it cites.
Path finding ii: An \ \backslash ˜ o (m sqrt (n)) algorithm for the minimum cost flow problem
Yin Tat Lee and Aaron Sidford · 2013
Later among the works it cites.
Navigating central path with electrical flows: From flows to matchings, and back
Aleksander Madry · 2013
Later among the works it cites.
Vertex sparsification and oblivious reductions
Ankur Moitra · 2013
Later among the works it cites.
Approximate maximum flow on separable undirected graphs
Gary L. Miller and Richard Peng · 2013
Later among the works it cites.
Solving sdd linear systems in nearly mlog1/2n time
Michael B. Cohen, Rasmus Kyng, Gary L. Miller, Jakub W. Pachocki, Richard Peng, Anup B. Rao, and Shen Chen Xu · 2014
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
D. Spielman and N. Srivastava · 2011
Cited alongside, same era.
Spectral sparsification of graphs
D. Spielman and S. Teng · 2011
Cited alongside, same era.
Twice-Ramanujan sparsifiers
Joshua Batson, Daniel A Spielman, and Nikhil Srivastava · 2012
Cited alongside, same era.
Faster approximate multicommodity flow using quadratically coupled flows
Jonathan A. Kelner, Gary L. Miller, and Richard Peng · 2012
Cited alongside, same era.
An algebraic multigrid method with guaranteed convergence rate
Artem Napov and Yvan Notay · 2012
Cited alongside, same era.
Efficient preconditioning of laplacian matrices for computer graphics
Dilip Krishnan, Raanan Fattal, and Richard Szeliski · 2013
Cited alongside, same era.
A simple, combinatorial algorithm for solving sdd systems in nearly-linear time
Jonathan A Kelner, Lorenzo Orecchia, Aaron Sidford, and Zeyuan Allen Zhu · 2013
Cited alongside, same era.
Later among the works it cites.
Uniform sampling for matrix approximation
Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford · 2014
Later among the works it cites.
Simple parallel and distributed algorithms for spectral graph sparsification
Ioannis Koutis · 2014
Later among the works it cites.
An efficient parallel solver for SDD linear systems
Richard Peng and Daniel A. Spielman · 2014
Later among the works it cites.
Nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
Daniel A. Spielman and Shang-Hua Teng · 2014
Later among the works it cites.
Spectral sparsification and regret minimization beyond matrix multiplicative updates
Zeyuan Allen-Zhu, Zhenyu Liao, and Lorenzo Orecchia · 2015
Closest in time.
Interlacing families IV: Bipartite Ramanujan graphs of all sizes
Adam W Marcus, Nikhil Srivastava, and Daniel A Spielman · 2015
Closest in time.