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 toolSolutionA Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
Spielman D, Teng S. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal On Computing 2013, 42: 1-26. DOI: 10.1137/080744888.Peer-Reviewed Original ResearchLinear time algorithmMassive graphsTime algorithmLinear system solverRunning timeSubset of verticesLinear systemsSpectral sparsifierLaplacian matrixNumber edgesSparsest cutSystem solverCorresponding eigenvectorsLocal clustering algorithmSmallest eigenvalueDominant matricesClustering algorithmPartitioning algorithmGraph partitioningWhole graphGraph algorithmsLocal algorithmGraphVerticesBetter clusters
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
2004
Nearly-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 Research
2001
A Simple Method for Evaluating Partition Functions of Linear Polymers
Kong Y. A Simple Method for Evaluating Partition Functions of Linear Polymers. The Journal Of Physical Chemistry B 2001, 105: 10111-10114. DOI: 10.1021/jp011758n.Peer-Reviewed Original Research
1999
General recurrence theory of ligand binding on a three-dimensional lattice
Kong Y. General recurrence theory of ligand binding on a three-dimensional lattice. The Journal Of Chemical Physics 1999, 111: 4790-4799. DOI: 10.1063/1.479242.Peer-Reviewed Original ResearchTransfer matrix MLinear latticeMatrix MCircular latticePartition functionRecurrence relationsThree-dimensional lattice modelThree-dimensional latticeStatistical mechanicsLinear systemsSecular equationRecurrence theoryTransfer matrixLattice modelGeneral theorySimple geometryPeriodical boundary conditionsBoundary conditionsMatrix sizeEigenvaluesLatticeSimple structureUnique binding configurationsTwo-dimensional layersTheory
1998
Multiscale Inversion of Elliptic Operators
Averbuch A, Beylkin G, Coifman R, Israeli M. Multiscale Inversion of Elliptic Operators. Wavelet Analysis And Its Applications 1998, 7: 341-359. DOI: 10.1016/s1874-608x(98)80013-7.Peer-Reviewed Original ResearchLinear systemsCondition numberElliptic partial differential equationsPartial differential equationsLarge condition numberBoundary conditionsConjugate gradient iterationNumber of iterationsFast adaptive algorithmNumber of operationsDifferential equationsWavelet coordinatesSuch equationsMultiscale inversionDifferential operatorsElliptic operatorsDiagonal preconditionerComplicated equationsPeriodic boundary conditionsGradient iterationPoisson equationGradient algorithmConjugate directionsEquationsAdaptive algorithm
This site is protected by hCaptcha and its Privacy Policy and Terms of Service apply