2014
Nearly 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
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 system
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