Algorithm sees massive leap in complex number crunching

 

Gallery

By Stewart Mitchell

Posted on 22 Oct 2010 at 09:21

Computer scientists at Carnegie Mellon University claim they have devised an algorithm that will reduce problem-solving times a billion-fold in the complex world of linear equations.

According to the scientists, the theoretical breakthrough has huge practical potential in the linear systems used to model real-world systems, such as transportation, energy, telecommunications and manufacturing.

The Carnegie Mellon team said the new algorithm employs tools from graph theory, randomised algorithms and linear algebra to allow stunning increases in speed.

The scientists claim the algorithm, which applies to problems known as symmetric diagonally dominant (SDD) systems, is so efficient that “it may soon be possible for a desktop workstation to solve systems with a billion variables in just a few seconds”.

SSD is used in applications such as recommendation engines on Amazon or Netflix, but also in image processing operations and engineering applications.

"The new linear system solver is wonderful both for its speed and its simplicity," said Daniel Spielman, a professor of applied mathematics and computer science at Yale, who peer reviewed the project.

"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."

The team's approach to solving SDD systems is to first solve a simplified system that can be done rapidly and serve as a "pre-conditioner" to guide iterative steps to an ultimate solution.

The team’s research paper (pdf) shows that the method can be a bilion times faster than one classical method of working on linear problems.