news
Science | DOI: 10.1145/1995376.1995382
Kirk L. Kroeker
a Breakthrough in
algorithm Design
Computer scientists at Carnegie Mellon University have devised an
algorithm that might be able to solve a certain class of linear systems
much more quickly than today’s fastest solvers.
SYstems Of linear equa- tions are everywhere. They are used in telecommuni- cations, transportation, manufacturing, and many
other domains. The algorithms used
to solve linear systems must be able to
compute solutions to equations involving millions—or sometimes billions—
of variables. Because calculating
solutions for these systems is time-consuming on even the fastest computers, finding ways to accelerate these
computations is an ongoing challenge
for algorithm designers. Now, a group
of computer scientists at Carnegie
Mellon University (CMU) have devised
an algorithm they say might be able to
solve a certain class of linear systems
much more quickly than today’s fastest solvers.
The researchers say the algorithm,
which applies to a class of problems
known as symmetric and diagonally
dominant (SDD) systems, not only has
practical potential, but also is so fast it
might soon be possible for a desktop PC
to solve systems with one billion vari-
ables in just seconds. “The main point
of the new algorithm is that it is guaran-
teed to work and to work quickly,” says
image processing. Algorithms used
for this type of linear system fall into
two broad classes: direct solvers, such
as Gaussian elimination, and iterative
solvers. In contrast to direct solvers,
which compute exact solutions, itera-
tive solvers produce a series of approxi-
mate solutions. Direct methods are
usually memory-hungry, a limitation
that makes iterative solvers, such as the
kind developed by the CMU team, more
effective for the large data sets gener-
ated by today’s applications.
Gary L. Miller, a professor of computer
science at CMU and a member of the
three-person team that developed the
new algorithm.
SDD systems, characterized by system matrices in which each diagonal element is larger than the sum of the absolute values of all the other elements
in the corresponding row, are used for
a wide range of purposes, from online
recommendation systems to industrial
simulations, materials modeling, and
a linear system designed to improve the quality of retinal image segmentation through the
use of an iterative solver technique called spectral rounding, developed at Carnegie mellon
University and the University of Pittsburgh medical Center. Conventional segmentation
algorithms tend to fail in the presence of retinal abnormalities. on the left is the input image.
on the right is the segmented image.
