- Reaction score
- 1,712
Grade school math students are likely familiar with teachers admonishing them 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.
“This is one of the most fundamental problems in computing,” said Mark Giesbrecht of the University of Waterloo. “Now we have a proof that we can go faster.”
The new method, by Richard Peng and Santosh Vempala of the Georgia Institute of Technology, was posted online in July and presented in January at the annual ACM-SIAM Symposium on Discrete Algorithms, where it won the best-paper award.
Linear systems involve two or more equations with variables that specify the different ways things relate to each other. They’re “linear” because the only allowable power is exactly 1 and graphs of solutions to the equations form planes.
A common example of a linear system — also likely familiar to math students — involves a barnyard filled with chickens and pigs. If you only know there are 10 heads and 30 feet, how many chickens are there, and how many pigs? As algebra students learn, there’s a set procedure for figuring it out: Write down two algebraic equations and solve them together.
But linear systems can do more than just count chickens and pigs. They crop up in many practical settings, where building a sturdier bridge or a stealthier aircraft can involve solving systems with millions of interdependent linear equations. More fundamentally, linear systems feature in many basic optimization problems in computer science that involve finding the best values for a set of variables within a system of constraints. If we can solve linear systems faster, then we can solve those problems faster too.
www.quantamagazine.org
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.
“This is one of the most fundamental problems in computing,” said Mark Giesbrecht of the University of Waterloo. “Now we have a proof that we can go faster.”
The new method, by Richard Peng and Santosh Vempala of the Georgia Institute of Technology, was posted online in July and presented in January at the annual ACM-SIAM Symposium on Discrete Algorithms, where it won the best-paper award.
Linear systems involve two or more equations with variables that specify the different ways things relate to each other. They’re “linear” because the only allowable power is exactly 1 and graphs of solutions to the equations form planes.
A common example of a linear system — also likely familiar to math students — involves a barnyard filled with chickens and pigs. If you only know there are 10 heads and 30 feet, how many chickens are there, and how many pigs? As algebra students learn, there’s a set procedure for figuring it out: Write down two algebraic equations and solve them together.
But linear systems can do more than just count chickens and pigs. They crop up in many practical settings, where building a sturdier bridge or a stealthier aircraft can involve solving systems with millions of interdependent linear equations. More fundamentally, linear systems feature in many basic optimization problems in computer science that involve finding the best values for a set of variables within a system of constraints. If we can solve linear systems faster, then we can solve those problems faster too.
New Algorithm Breaks Speed Limit for Solving Linear Equations
By harnessing randomness, a new algorithm achieves a fundamentally novel — and faster — way of performing one of the most basic computations in math and computer science.
www.quantamagazine.org
Last edited by a moderator:
