杏吧原创

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鈥檚 computers, it is a surprising theoretical leap that could one day have myriad applications. And it鈥檚 creating quite a splash on the mathematical blogosphere.

鈥淎ll this is extremely exciting, and is one of the best results proved in years in all of theory,鈥� , a computer scientist at the Georgia Institute of Technology in Atlanta, on his blog.

鈥淚 actually knew a month ago that this was coming 鈥� I had a hell of a time keeping the secret,鈥� , 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. The simplest way of multiplying two n 脳 n matrices 鈥� those with n rows and n columns 鈥� takes roughly n³ steps, but in 1969, Volker Strassen discovered an algorithm that did it in n^2.807 steps.

Matrix multiplication is generally performed using the simple n³ method or using Strassen鈥檚 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 2.376.

Buried solution

Now, , who splits her time between the University of California, Berkeley, and Stanford University, has shown this assumption was wrong 鈥� by tweaking the algorithm to .

The idea behind the improvement was actually present in Coppersmith and Winograd鈥檚 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. 鈥淭his led people to believe that higher levels of recursion won鈥檛 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鈥檛 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. 鈥淚t wasn鈥檛 intentional that I didn鈥檛 publicise it,鈥� he says.

Mathematical toolbox

When Vassilevska-Williams, who was working independently, came across Stothers鈥檚 thesis, she realised she could use part of his work. She applied the starting algorithm eight times to discover the final omega value of 2.373.

Is it worth getting excited over such a small improvement? 鈥淵es, because it has stood for so long and many people have worked on it,鈥� says , a computer scientist at the University of Maryland in College Park. 鈥淥ften theorists work on problems that people don鈥檛 really care about. This is not the case here.鈥�

Although today鈥檚 computers can鈥檛 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. 鈥淵ou can think of this as a new tool to be added to the toolbox,鈥� she says

Reference:

This article has been edited since it was first posted