ing principle of sorts in this area of research. The idea is to solve computations on a massive linear system by quickly running computations on a sparser system that in some well-defined algebraic sense is similar to the larger one. The sparser system used to set up these computations for the larger system is called the preconditioner.

Producing the sparse matrix requires zeroing out some of the nonzero entries and increasing the weight of others in the larger matrix. “One key ingredient in the newer algorithms is the judicious use of randomization to determine which entries are zeroed out,” explains Miller, who likens the CMU algorithm’s process of sparsification to “flipping a biased coin” to determine the fate of an element in the system matrix. This sparsification process is designed to create a representation of the larger system matrix to generate the preconditioner that will guide later computations.

While finding a preconditioner
might seem straightforward, finding a
good one is not. A reliable method for
finding a good preconditioner to ac-
celerate computations on large system
matrices is an ongoing challenge in
math and computer science. Methods
that rely on heuristics, for example,
have been effective, but only to a lim-
ited extent. “Heuristic solvers are often
guided by good intuition,” says Richard
Peng, a graduate student in the CMU
computer science department and a
member of the new algorithm team.
“However, the critical missing pieces of
understanding make them unreliable,
especially with the large and complicat-
ed systems that we face today.”

 

the spielman-teng solver The path to developing a more effective method than heuristics for finding a good preconditioner dates to the early 1990s and a series of ideas that suggested viewing SDD systems as combinatorial graphs. Research projects in spectral graph theory and numerical analysis developed these ideas in a string of new theories that, in 2004,

an application designed to improve the quality of optical coherence tomography images for an automated cartilage health-assessment routine. the top images represent the input. the bottom images, enhanced with a linear system designed to smooth the optical coherence tomography images, show striations in the cartilage that are indicative of unhealthy tissue.

emerged as what was widely considered to be a breakthrough proof by Daniel Spielman and Shang-Hua Teng. Spielman and Teng were able to prove that every SDD matrix has a good and discoverable preconditioner.

To put the idea into electrical terms,
Spielman and Teng showed that for a
given electrical network, there will be
one that uses fewer resistors while hav-
ing the same reliability and energy-con-
sumption properties as the original.
“The Spielman-Teng solver is asymp-
totically much faster than everything
that was known before,” says Peng. “It
is faster than previous solvers for all sys-
tems larger than a fixed size, and that
difference in speed increases as the sys-
tem becomes larger.”
Building on Spielman and Teng’s
work, the CMU team developed their
new algorithm that, from a mathemati-
cal point of view, is more concise, tak-
ing only five pages to detail instead of
50. “It’s nearly optimal,” says Ioannis
Koutis, the third member of the CMU
team and now a professor of computer
science at the University of Puerto Rico,
Rio Piedras. “We know that we can’t do
much better, if that’s possible at all.”
Due to its simplicity, along with
its promise of significant speed im-
provements over earlier algorithms,
the new solver made headlines when
it was introduced last October at the
IEEE 51st Annual Symposium on
Foundations of Computer Science
(FOCS). With an optimized imple-
mentation, the researchers say, the al-
gorithm would be some 10 to 20 times
faster than other solvers for current
problems. (The technical details of
the algorithm are in the FOCS paper;
see I. Koutis, G.L. Miller, and R. Peng,
“Approaching Optimality for Solving
SDD Linear Systems.”)

Spielman, a professor of applied mathematics and computer science at Yale University, says the CMU algorithm represents a significant improvement for solving SDD systems. “It is the first algorithm for this problem that is both provably fast in an asymptotic sense and that could be fast in practice,” he says.

Spielman explains that when he and Teng created their initial approach to this problem in 2004, their algorithm was guaranteed to find solutions in near-linear time. However, this guaran-