2016
Sparsified Cholesky and multigrid solvers for connection laplacians
Kyng R, Lee Y, Peng R, Sachdeva S, Spielman D. Sparsified Cholesky and multigrid solvers for connection laplacians. 2016, 842-850. DOI: 10.1145/2897518.2897640.Peer-Reviewed Original ResearchSystem of equationsConnection LaplacianNonzero matrix entriesApproximate inverseLinear time algorithmMultigrid algorithmMultigrid solverLinear equationsLaplacian matrixGaussian eliminationGraph LaplacianMatrix entriesLU factorizationNonzero entriesStrong approximationOriginal matrixLinear numberEquationsLaplacianLinear timeTime algorithmNew algorithmAlgorithmCholeskyFactorization
2014
Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
Spielman D, Teng S. Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems. SIAM Journal On Matrix Analysis And Applications 2014, 35: 835-885. DOI: 10.1137/090771430.Peer-Reviewed Original ResearchDiagonal entriesInverse power methodLinear system solverDominant linear systemsLower asymptotic complexityLinear systemsLinear time algorithmNonzero structureCondition numberSystem solverDominant matricesFiedler vectorNonzero entriesPreconditionerAsymptotic complexityDevelopment of algorithmsRandomized algorithmSpecial casePower methodIntroduction of algorithmsRecursive fashionTime algorithmAlgorithmMatrixSolverTwice-Ramanujan Sparsifiers
Batson J, Spielman D, Srivastava N. Twice-Ramanujan Sparsifiers. SIAM Review 2014, 56: 315-334. DOI: 10.1137/130949117.Peer-Reviewed Original ResearchSpectral sparsifierLaplacian matrixPositive semidefinite matricesNonnegative diagonal matrixNumber of edgesNumber of verticesDeterministic polynomial time algorithmGeneral theoremSemidefinite matricesNonzero entriesPolynomial time algorithmSparse graphsDiagonal matrixQuadratic formSparse approximationSparsifiersWeighted graphReal matricesSpecial caseTime algorithmGraphVerticesMatrixTheoremApproximation
2013
A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
Spielman D, Teng S. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal On Computing 2013, 42: 1-26. DOI: 10.1137/080744888.Peer-Reviewed Original ResearchLinear time algorithmMassive graphsTime algorithmLinear system solverRunning timeSubset of verticesLinear systemsSpectral sparsifierLaplacian matrixNumber edgesSparsest cutSystem solverCorresponding eigenvectorsLocal clustering algorithmSmallest eigenvalueDominant matricesClustering algorithmPartitioning algorithmGraph partitioningWhole graphGraph algorithmsLocal algorithmGraphVerticesBetter clusters
2012
Twice-Ramanujan Sparsifiers
Batson J, Spielman D, Srivastava N. Twice-Ramanujan Sparsifiers. SIAM Journal On Computing 2012, 41: 1704-1721. DOI: 10.1137/090772873.Peer-Reviewed Original Research
2008
Graph sparsification by effective resistances
Spielman D, Srivastava N. Graph sparsification by effective resistances. 2008, 563-568. DOI: 10.1145/1374376.1374456.Peer-Reviewed Original Research
2004
Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
Spielman D, Teng S. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. 2004, 81-90. DOI: 10.1145/1007352.1007372.Peer-Reviewed Original Research