Linear Equation Algorithm Shatters Computer Run Time

October 22, 2010

Combining mathematics of graph theory, randomization, and linear algebra, computer scientists have devised a lightning fast algorithm for solving systems of linear equations.

Gary Miller, Ioannis Koutis, and Richard Peng (all at Carnegie Mellon University) came up with the algorithm, which deals with a class of problems called symmetric diagonally dominant linear systems. Its run time is said to be a billion times faster than any based on Gaussian elimination.

According to a recent article in Dr. Dobbs, “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.”

Applications involve image processing, logistics, scheduling, recommendation systems (such as those used by Netflix and Amazon.com), transportation, energy, telecommunications, and manufacturing.

"The new linear system solver of Koutis, Miller, and Peng is wonderful both for its speed and its simplicity," said algorithm expert Daniel Spielman (Yale University). "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."

Source: Dr. Dobbs (October 21, 2010)