Sign In

Communications of the ACM

ACM Careers

Algorithm Breaks Speed Limit for Solving Linear Equations

background of math equations

Credit: Getty Images

Grade school math teachers admonish students not to just guess the answer to a problem. But a new proof establishes that, in fact, the right kind of guessing is sometimes the best way to solve systems of linear equations, one of the bedrock calculations in math.

As a result, the proof establishes the first method capable of surpassing what had previously been a hard limit on just how quickly some of these types of problems can be solved.

The new method, by Richard Peng and Santosh Vempala of the Georgia Institute of Technology, is decribed in "Solving Sparse Linear Systems Faster Than Matrix Multiplication," which was presented at SODA21, the ACM-SIAM Symposium on Discrete Algorithms, where it won the best-paper award.

From Quanta Magazine
View Full Article


No entries found

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account