Communications of the ACM
Algorithm Breaks Speed Limit for Solving Linear 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