Now you have three equations and three unknowns. The numbers, or coefficients, in front of each variable reflect the quantity of that attribute possessed by each animal. To proceed, assign a variable to each animal ( c for chickens, r for rhinos, g for goats) and write an equation for each attribute.
Can you figure out how many there are of each animal? You do a quick count and determine there are 12 heads, 38 feet and 10 horns. To get a feel for linear systems and how you might solve them, return to the barnyard, but imagine it’s more of a menagerie now: chickens, 1-horned rhinos and 2-horned goats. And no teacher would be mad at you for it. “You can guess your way to solutions,” said Peng. The authors couple it with a new approach that, in essence, is a form of trained divination. It still features in the work, but in a complementary role. That technique, called matrix multiplication, previously set a hard speed limit on just how quickly linear systems could be solved. The new proof finds a quicker way of solving a large class of linear systems by sidestepping one of the main techniques typically used in the process. “Linear systems are the workhorse of modern computation,” said Vempala. If we can solve linear systems faster, then we can solve those problems faster too. 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. 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. 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.īut linear systems can do more than just count chickens and pigs. They’re “linear” because the only allowable power is exactly 1 and graphs of solutions to the equations form planes.Ī common example of a linear system - also likely familiar to math students - involves a barnyard filled with chickens and pigs. Linear systems involve two or more equations with variables that specify the different ways things relate to each other. 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. “Now we have a proof that we can go faster.” “This is one of the most fundamental problems in computing,” said Mark Giesbrecht of the University of Waterloo.
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.Īs 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. Grade school math students are likely familiar with teachers admonishing them not to just guess the answer to a problem.
0 kommentar(er)
