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 workAlgorithmMatrixSparsifiersSolverInverseSystem
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