Relevant Links
Press Release
Research Papers
Media Contact
Keywords
SDD systems, symmetric diagonally dominant systems, linear systems, spectral graph theory
Buzz
COMPUTING RESEARCH HIGHLIGHT OF THE WEEK [November 19 - 23, 2010]
Speedy Algorithm for Linear Systems
Computer scientists at Carnegie Mellon University have devised an innovative and elegantly concise algorithm that can efficiently solve systems of linear equations that are critical to such important computer applications as image processing, logistics and scheduling problems, and recommendation systems.
The theoretical breakthrough by Professor Gary Miller, Systems Scientist Ioannis Koutis and Ph.D. student Richard Peng, all of Carnegie Mellon's Computer Science Department, has enormous practical potential. Linear systems are widely used to model real-world systems, such as transportation, energy, telecommunications and manufacturing that often may include millions, if not billions, of equations and variables.
The new algorithm, which applies to an important class of problems known as symmetric diagonally dominant (SDD) systems, employs powerful new tools from graph theory, randomized algorithms and linear algebra. It 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.
A number of SDD solvers exist, but they tend not to work across the broad class of SDD problems and are prone to failures, while the randomized algorithm developed by Miller, Koutis and Peng applies across the spectrum of SDD systems. The team's approach 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.
The result is a significant decrease in computer run times. The algorithm's run time would be about a billion times faster than classic Gaussian elimination for a sparse system of 1 million terms. Other, newer algorithms are faster than Gaussian elimination, but none promise the same speed as the Carnegie Mellon algorithm.
Researchers:
Gary L. Miller (Carnegie Mellon University)
Ioannis Koutis (Carnegie Mellon University)
Richard Peng (Carnegie Mellon University)
Agencies (that have supported the research):
Carnegie Mellon University, National Science Foundation, Microsoft Research, Natural Sciences and Engineering Research Council of Canada
‹ Current Highlight | Past Highlights ›
Computing Research Highlight of the Week is a service of the Computing Community Consortium and the Computing Research Association designed to highlight some of the exciting and important recent research results in the computing fields. Each week a new highlight is chosen by CRA and CCC staff and volunteers from submissions from the computing community. Want your research featured? Submit it!.
