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
Twice-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
Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations
Spielman D. Algorithms, Graph Theory, and the Solution of Laplacian Linear Equations. Lecture Notes In Computer Science 2012, 7392: 24-26. DOI: 10.1007/978-3-642-31585-5_5.Peer-Reviewed Original ResearchTwice-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
2011
Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
Christiano P, Kelner J, Madry A, Spielman D, Teng S. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. 2011, 273-282. DOI: 10.1145/1993636.1993674.Peer-Reviewed Original Research
2007
Spectral partitioning works: Planar graphs and finite element meshes
Spielman D, Teng S. Spectral partitioning works: Planar graphs and finite element meshes. Linear Algebra And Its Applications 2007, 421: 284-305. DOI: 10.1016/j.laa.2006.07.020.Peer-Reviewed Original ResearchBounded-degree planar graphsPlanar graphsSpectral partitioning methodLaplacian matrixSmallest eigenvalueFinite element meshRatio of verticesClass of graphsDimensional meshesElement meshSpectral partitioning techniquesNumerical algorithmFiedler vectorPartitioning methodSmall separatorsTwo-dimensional meshEdge cutGraphSpectral bisectionEigenvaluesPartitioning techniquesMeshBoundsEigenvectorsMatrix
1996
Spectral partitioning works: planar graphs and finite element meshes
Spielman D, Teng S. Spectral partitioning works: planar graphs and finite element meshes. 2011 IEEE 52nd Annual Symposium On Foundations Of Computer Science 1996, 96-105. DOI: 10.1109/sfcs.1996.548468.Peer-Reviewed Original ResearchBounded-degree planar graphsPlanar graphsSpectral partitioning methodLaplacian matrixSmallest eigenvalueFinite element meshRatio of verticesClass of graphsDimensional meshesElement meshSpectral partitioning techniquesNumerical algorithmFiedler vectorPartitioning methodSmall separatorsTwo-dimensional meshEdge cutGraphSpectral bisectionEigenvaluesPartitioning techniquesMeshEigenvectorsBoundsMatrix