Algorithm sees massive leap in complex number crunching
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.
- Is it worth upgrading a media centre to Windows 8?
- Flickr redesign: is it enough to tempt photographers back?
- Hands on with the new Google Maps
- Nokia Lumia 925 review: first look
- Why I won't subscribe to Creative Cloud
- GoPro camera strapped to a remote-control helicopter: the ultimate boy's toy
- Acer Iconia A1 review: first look
- Acer Aspire P3 review: first look
- Acer Aspire R7 review: first look
- How we produce the PC Pro podcast
- The ICO's shame-faced u-turn on cookies
- Start8 and ModernMix: making Windows 8 work on a desktop
- How to boost your mobile reception
- How to fix Facebook: Social Fixer
- Taking the stress out of WordPress updates
- Where to download free web fonts
- Turn your tablet into a Sky+ remote control
- How to measure the success of a new IT system
- Three years on: the state of the tablet market
- Windows 8: what works and what doesn't