Announced by Carnegie Mellon University:
http://www.cmu.edu/news/archive/2010/October/oct21_speedyalgorithm.shtml
http://www.cs.cmu.edu/~glmiller/Publications/Papers/KoutisApproaching-2010.pdf
From the Article:
The algorithm, which applies to an important class of problems known as symmetric diagonally dominant (SDD) systems, is so efficient that it may soon be possible for a desktop workstation to solve systems with a billion variables in just a few seconds.
A number of SDD solvers have been developed, but they tend not to work across the broad class of SDD problems and are prone to failures. The randomized algorithm developed by Miller, Koutis and Peng, however, applies across the spectrum of SDD systems.
The team’s approach to solving SDD systems is to first solve a simplified system that can be done rapidly and serve as a “preconditioner” to guide iterative steps to an ultimate solution. To construct the preconditioner, the team uses new ideas from spectral graph theory, such as spanning tree and random sampling.
The result is a significant decrease in computer run times. The Gaussian elimination algorithm runs in time proportional to s3, where s is the size of the SDD system as measured by the number of terms in the system, even when s is not much bigger the number of variables. The new algorithm, by comparison, has a run time of s[log(s)]2. That means, if s = 1 million, that the new algorithm run time would be about a billion times faster than Gaussian elimination.
Other algorithms are better than Gaussian elimination, such as one developed in 2006 by Daniel Spielman of Yale University and Miller’s former student, Shang-Hua Teng of the University of Southern California, which runs in s[log(s)]25. But none promise the same speed as the one developed by the Carnegie Mellon team.
“The new linear system solver of Koutis, Miller and Peng is wonderful both for its speed and its simplicity,” said Spielman, a professor of applied mathematics and computer science at Yale. “There is no other algorithm that runs at even close to this speed. In fact, it’s impossible to design an algorithm that will be too much faster.”