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