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