2016
Graphs, Vectors, and Matrices
Spielman D. Graphs, Vectors, and Matrices. Bulletin Of The American Mathematical Society 2016, 54: 45-61. DOI: 10.1090/bull/1557.Peer-Reviewed Original Research
2014
An efficient parallel solver for SDD linear systems
Peng R, Spielman D. An efficient parallel solver for SDD linear systems. 2014, 333-342. DOI: 10.1145/2591796.2591832.Peer-Reviewed Original ResearchSystem of equationsEfficient parallel solverLinear systemsLinear equationsLow-stretch spanning treesSDD matrixDominant matricesParallel solverInput matrixSparse matricesFast algorithmPolylogarithmic timeParallel algorithmEquationsFirst parallel algorithmSpanning treeLinear workAlgorithmMatrixSparsifiersSolverInverseSystemNearly 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
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 Research
2007
Spectral Graph Theory and its Applications
Spielman D. Spectral Graph Theory and its Applications. 2007, 29-38. DOI: 10.1109/focs.2007.56.Peer-Reviewed Original ResearchSpectral 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
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
1997
A remark on matrix rigidity
Shokrollahi M, Spielman D, Stemann V. A remark on matrix rigidity. Information Processing Letters 1997, 64: 283-285. DOI: 10.1016/s0020-0190(97)00190-7.Peer-Reviewed Original Research
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