|
|
A Breakthrough in Algorithm Design
By Kirk L. Kroeker
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 equations are everywhere. They are used
in telecommunications, 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) has devised an algorithm
that the researchers say might be able to solve a certain
class of linear systems much more quickly than today’s
fastest solvers.
(This article appeared in
CACM, vol. 54, no. 9, September 2011, pp. 13-15.)
(download
the PDF)
|
