In this case we have three variables, so it takes 3 3, or 27, computational steps. That number is the cube of the number of variables in the system ( n 3). Whether you manipulate the equations or take the matrix route, you’ll end up performing the same total number of computational steps to solve the problem. We can combine these three matrices into a single linear system, where the first matrix multiplied by the unknown values of the second matrix equals the third matrix - at which point we can use linear algebra to solve for the second matrix. Next, we represent the unknown number of chickens, rhinos and goats with another matrix.įinally, we represent the observed number of heads, feet and horns with a third matrix. The three equations turn into this matrix. Then you can repeat the process, leveraging the one variable you’ve solved for to solve for the next.īut another, more sophisticated, way to proceed is to create a matrix whose entries are the coefficients of the equations. Substitute that value for r in the other two equations and continue like this until you’ve defined all variables in terms of just one variable, which you can then solve for exactly. For example, 0 c + 1 r + 2 g = 10 turns into r = 10 – 2 g. One way to solve them is to manipulate one equation and define one variable in terms of the other two. 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)
