460
Relations, Functions, and Matrices
speCiaL iNterest paGe
Solve Millions of equations, Faster than gauss
Systems of linear equations are used in many areas of
application, including telecommunications, materials
analysis, transportation, economics, and medical imaging. Instead of systems of 3 or 4 linear equations
with 3 or 4 unknowns, such as we saw in our Example
problems, the value of n in such applications can go
into the millions or billions. In Exercise 55 of Section
5.7, we see that a worst-case analysis of Gaussian elimination results in Θ(n
3
) computations (multiplications
and additions). Such computations on real numbers are
called floating point operations. The overall implication of an algorithm of Θ(n
3
) is that increasing the size
of n by a factor of 10 increases the work by a factor of
10
3
= 1000.
If n has a value of 1 billion, n = 10
9
, then n
3
= 10
27
.
Suppose we find a way to parallelize the Gaussian
elimination algorithm and run it on a fast parallelprocessing supercomputer. The Chinese Tianhe-2,
the world’s fastest supercomputer as of June 2013 can
crank out about 33.86 petaflops (33.86 × 10
15
floatingpoint operations per second). The worst-case solution
would be bounded above by
10
27
operations
(33.86) * 10
15
operations∙second
= over 936 years!
Now Θ(n
3
) was an upper bound, so maybe the closer
value is something like (2∙3)Θ(n
3
), but at any rate it’s
clear that these are time-consuming problems, and
faster solution techniques are of interest.
Gaussian elimination produces exact solutions to
systems of linear equations. Other solution methods,
called iterative solvers, produce a series of approximate solutions that approach the exact solution. This
method sounds as if it would take even longer, but most
iterative solvers start out with a sparse matrix (a matrix
with many 0 entries) for which computations will be
faster but is nonetheless a good representative of the
information in the original augmented matrix. Deciding which values can be zeroed out while modifying
the values of the remaining coefficients so as to provide a good “preconditioner” for the eventual solution
is a difficult problem in itself.
A team of researchers at Carnegie Mellon University announced in 2010 that they had found a new algorithm for creating a good preconditioner for a large
system of linear equations of a certain type, called
SDD (symmetric and diagonally dominant) systems.
In a diagonally dominant matrix, the absolute value
of the diagonal element (a ii ) of each row of a matrix
is bigger than the sum of the absolute values of all
other elements in that row. SDD systems turn out to
have many important applications, such as maximizing flow through a network (a computer network, a
water pipeline system, a transportation system) and
recommendation systems such as Netflix that suggest
movies you might like based on your past preferences
and other user data. The new algorithm, based on sophisticated mathematical techniques, is approximately
Θ(n(log n)
2
)), nearly linear, promising much faster solutions to these massive problems.
“A Breakthrough in Algorithm Design,” Kroeker, K., Communications of the ACM, September 2011.
“A Fast Solver for a Class of Linear Systems,” Koutis, I.,
Miller, G. L., and Peng, R., Communications of the
ACM, October 2012.
“Approaching Optimality for Solving SDD Linear Systems,” Koutis, I., Miller, G. L., and Peng, R., Proceedings of the 2010 IEEE 51st Annual Symposium on
Foundations of Computer Science, Las Vegas, NV,
October 23–26, 2010.
Linear Equation Breakthrough, Dr. Dobbs, http://drdobbs.
com/architecture-and-design/227900457
C h a p t e r
5 5
Relations, Functions, and Matrices
speCiaL iNterest paGe
Solve Millions of equations, Faster than gauss
Systems of linear equations are used in many areas of
application, including telecommunications, materials
analysis, transportation, economics, and medical imaging. Instead of systems of 3 or 4 linear equations
with 3 or 4 unknowns, such as we saw in our Example
problems, the value of n in such applications can go
into the millions or billions. In Exercise 55 of Section
5.7, we see that a worst-case analysis of Gaussian elimination results in Θ(n
3
) computations (multiplications
and additions). Such computations on real numbers are
called floating point operations. The overall implication of an algorithm of Θ(n
3
) is that increasing the size
of n by a factor of 10 increases the work by a factor of
10
3
= 1000.
If n has a value of 1 billion, n = 10
9
, then n
3
= 10
27
.
Suppose we find a way to parallelize the Gaussian
elimination algorithm and run it on a fast parallelprocessing supercomputer. The Chinese Tianhe-2,
the world’s fastest supercomputer as of June 2013 can
crank out about 33.86 petaflops (33.86 × 10
15
floatingpoint operations per second). The worst-case solution
would be bounded above by
10
27
operations
(33.86) * 10
15
operations∙second
= over 936 years!
Now Θ(n
3
) was an upper bound, so maybe the closer
value is something like (2∙3)Θ(n
3
), but at any rate it’s
clear that these are time-consuming problems, and
faster solution techniques are of interest.
Gaussian elimination produces exact solutions to
systems of linear equations. Other solution methods,
called iterative solvers, produce a series of approximate solutions that approach the exact solution. This
method sounds as if it would take even longer, but most
iterative solvers start out with a sparse matrix (a matrix
with many 0 entries) for which computations will be
faster but is nonetheless a good representative of the
information in the original augmented matrix. Deciding which values can be zeroed out while modifying
the values of the remaining coefficients so as to provide a good “preconditioner” for the eventual solution
is a difficult problem in itself.
A team of researchers at Carnegie Mellon University announced in 2010 that they had found a new algorithm for creating a good preconditioner for a large
system of linear equations of a certain type, called
SDD (symmetric and diagonally dominant) systems.
In a diagonally dominant matrix, the absolute value
of the diagonal element (a ii ) of each row of a matrix
is bigger than the sum of the absolute values of all
other elements in that row. SDD systems turn out to
have many important applications, such as maximizing flow through a network (a computer network, a
water pipeline system, a transportation system) and
recommendation systems such as Netflix that suggest
movies you might like based on your past preferences
and other user data. The new algorithm, based on sophisticated mathematical techniques, is approximately
Θ(n(log n)
2
)), nearly linear, promising much faster solutions to these massive problems.
“A Breakthrough in Algorithm Design,” Kroeker, K., Communications of the ACM, September 2011.
“A Fast Solver for a Class of Linear Systems,” Koutis, I.,
Miller, G. L., and Peng, R., Communications of the
ACM, October 2012.
“Approaching Optimality for Solving SDD Linear Systems,” Koutis, I., Miller, G. L., and Peng, R., Proceedings of the 2010 IEEE 51st Annual Symposium on
Foundations of Computer Science, Las Vegas, NV,
October 23–26, 2010.
Linear Equation Breakthrough, Dr. Dobbs, http://drdobbs.
com/architecture-and-design/227900457
C h a p t e r
5 5