preview.tinyurl.com/cdf5u32 -> www.newscientist.com/article/dn21255-key-mathematical-tool-sees-first-advance-in-24-years.html
Jacob Aron One of the most fundamental mathematical tools outside of everyday arithmetic has seen its first improvement in 24 years. Although the new method of matrix multiplication, an essential tool for solving problems in physics, economics and most areas of science, is not practical for use on today's computers, it is a surprising theoretical leap that could one day have myriad applications. And it's creating quite a splash on the mathematical blogosphere.
wrote Scott Aaronson, another computer scientist and blogger, based at the Massachusetts Institute of Technology. Reducing omega A matrix is an array of numbers, and matrix multiplication is a way of combining two matrices to produce a third - essentially regular multiplication kicked up a notch. Matrix multiplication is generally performed using the simple n^3 method or using Strassen's algorithm, which is more complex but also more efficient for large matrices, but theorists have tried many other ways to reduce the number of steps by finding a smaller value for the exponent, known as omega. In 1987, this culminated in what remained the fastest known algorithm for 24 years. It was developed by Don Coppersmith and Shmuel Winograd and put omega at 2376.
The idea behind the improvement was actually present in Coppersmith and Winograd's original method, which essentially involves applying a starting algorithm twice in a row. The trouble was, applying the algorithm a third time seemingly gave no improvement. "This led people to believe that higher levels of recursion won't give an improvement either," says Vassilevska-Williams, so they gave up. Each application of the algorithm involved solving increasing numbers of difficult equations, and with no pay-off at the end it didn't seem worth the hard work. Then in 2010, Andrew Stothers at the University of Edinburgh, UK, applied the algorithm four times as part of his PhD thesis - but buried the result deep in the write-up, ensuring that it went unnoticed by the wider mathematics community. He then left research to work in the financial services industry. "It wasn't intentional that I didn't publicise it," he says. Mathematical toolbox When Vassilevska-Williams, who was working independently, came across Stothers's thesis, she realised she could use part of his work. She applied the starting algorithm eight times to discover the final omega value of 2373. Is it worth getting excited over such a small improvement?
William Gasarch, a computer scientist at the University of Maryland in College Park. "Often theorists work on problems that people don't really care about. Although today's computers can't take advantage of this specific speed advance, Vassilevska-Williams has also created a mathematical framework that could allow for further theoretical improvements that might be practically useful for computing.
variety of licensing options available for use of articles and graphics we own the copyright to. Have your say Only subscribers may leave comments on this article.
|
http://csua.com/feed/