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
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 algorithmAlgorithmMatrixSolver
2013
Spectral sparsification of graphs
Batson J, Spielman D, Srivastava N, Teng S. Spectral sparsification of graphs. Communications Of The ACM 2013, 56: 87-94. DOI: 10.1145/2492007.2492029.Peer-Reviewed Original ResearchSpectral sparsificationApproximate maximum flowLinear systemsSpectral approximationLinear time algorithmCombinatorial optimizationGraph sparsificationLinear equationsDominant matricesArbitrary graphsSparse graphsFast solutionUndirected networksFast algorithmDevelopment of algorithmsSparsificationMinimum cutMaximum flowGraphApproximationAlgorithmEquationsOptimizationImportant toolSolution
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
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
2008
Faster approximate lossy generalized flow via interior point algorithms
Daitch S, Spielman D. Faster approximate lossy generalized flow via interior point algorithms. 2008, 451-460. DOI: 10.1145/1374376.1374441.Peer-Reviewed Original ResearchInterior-point algorithmSymmetric M-matricesFlow problemLinear systemsPoint algorithmLinear equationsM-matrixGeneralized maximum flow problemMinimum cost flow problemLinear system solverFast approximation algorithmMaximum flow problemNumber of edgesRatios of integersDiagonally Dominant MatricesSystem solverΕ-approximationOptimal costApproximation algorithmFast algorithmParameter rangeMaximum flowEquationsPrevious algorithmsAlgorithm
2007
PARALLEL DELAUNAY REFINEMENT: ALGORITHMS AND ANALYSES
SPIELMAN D, TENG S, ÜNGÖR A. PARALLEL DELAUNAY REFINEMENT: ALGORITHMS AND ANALYSES. International Journal Of Computational Geometry & Applications 2007, 17: 1-30. DOI: 10.1142/s0218195907002227.Peer-Reviewed Original Research
2006
Smoothed Analysis of Algorithms and Heuristics
Spielman D, Teng S. Smoothed Analysis of Algorithms and Heuristics. 2006, 274-342. DOI: 10.1017/cbo9780511721571.010.Peer-Reviewed Original ResearchSmoothed analysisAnalysis of algorithmsNumber of iterationsMathematical programmingCombinatorial optimizationComputational geometryApproximation algorithmIterative algorithmApproximation ratioRandomized algorithmDiscrete inputsPerturbation modelRandom bitsScientific computingError probabilityTime complexityCompetitive ratioNumber of callsAlgorithmOnline algorithmNumber of bitsOpen questionHeuristicsIterationComputation
2005
A Lower Bound on Convergence of a Distributed Network Consensus Algorithm
Cao M, Spielman D, Morse A. A Lower Bound on Convergence of a Distributed Network Consensus Algorithm. 2005, 2356-2361. DOI: 10.1109/cdc.2005.1582514.Peer-Reviewed Original Research
2004
Time complexity of practical parallel steiner point insertion algorithms
Spielman D, Teng S, Üngör A. Time complexity of practical parallel steiner point insertion algorithms. 2004, 267-268. DOI: 10.1145/1007912.1007953.Peer-Reviewed Original ResearchNearly-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 ResearchSmoothed analysis of algorithms
Spielman D, Teng S. Smoothed analysis of algorithms. Journal Of The ACM 2004, 51: 385-463. DOI: 10.1145/990308.990310.Peer-Reviewed Original Research
2003
Smoothed analysis of termination of linear programming algorithms
Spielman D, Teng S. Smoothed analysis of termination of linear programming algorithms. Mathematical Programming 2003, 97: 375-404. DOI: 10.1007/s10107-003-0448-9.Peer-Reviewed Original ResearchExponential algorithmic speedup by a quantum walk
Childs A, Cleve R, Deotto E, Farhi E, Gutmann S, Spielman D. Exponential algorithmic speedup by a quantum walk. 2003, 59-68. DOI: 10.1145/780542.780552.Peer-Reviewed Original ResearchQuantum algorithmsQuantum walkBlack-box settingGraph traversal problemTime quantum walkQuantum Fourier transformPrevious quantum algorithmsClassical computersQuantum computerTraversal problemContinuous-time quantum walkClassical algorithmsBox settingSubexponential timeAlgorithmic speedupQuantumAlgorithmComputerSpeedupDifferent techniquesGraphFourier transformSmoothed Analysis
Spielman D, Teng S. Smoothed Analysis. Lecture Notes In Computer Science 2003, 2748: 256-270. DOI: 10.1007/978-3-540-45078-8_23.Peer-Reviewed Original Research
2001
Min–max-boundary domain decomposition
Kiwi M, Spielman D, Teng S. Min–max-boundary domain decomposition. Theoretical Computer Science 2001, 261: 253-266. DOI: 10.1016/s0304-3975(00)00143-2.Peer-Reviewed Original ResearchDistributed-memory parallel computersK-SubgraphParallel computing techniquesDomain decompositionAmount of computationMin-maxComputing techniquesParallel computersLarge communicationGraph decompositionNumber of edgesSubgraphsAlgorithmPartitionComputerComputationCommunicationSpecial caseDecomposition amountGraph GMemory loadBoundary sizeDecompositionNumerical systemIntroduction to the Special Issue on Codes on Graphs and Iterative Algorithms
Frey B, Koetter R, Forney G, Kschischang F, Mceliece R, Spielman D. Introduction to the Special Issue on Codes on Graphs and Iterative Algorithms. IEEE Transactions On Information Theory 2001, 47: 493. DOI: 10.1109/tit.2001.910571.Peer-Reviewed Original ResearchEfficient Erasure Correcting Codes
Luby M, Mitzenmacher M, Shokrollahi M, Spielman D. Efficient Erasure Correcting Codes. IEEE Transactions On Information Theory 2001, 47: 569. DOI: 10.1109/18.910575.Peer-Reviewed Original Research
1998
Min-Max-Boundary Domain Decomposition
Kiwi M, Spielman D, Teng S. Min-Max-Boundary Domain Decomposition. Lecture Notes In Computer Science 1998, 1449: 137-147. DOI: 10.1007/3-540-68535-9_17.Peer-Reviewed Original ResearchDistributed-memory parallel computersParallel computing techniquesDomain decompositionAmount of computationComputing techniquesSubgraphs G1Parallel computersMemory requirementsPartitioning problemGraph decompositionNumber of edgesMin-maxAlgorithmSubgraphsPartitionComputerComputationCommunicationRequirementsSpecial caseDecomposition amountGraph GBoundary sizeDecompositionNumerical system