As a basic mathematical operation, the operation speed of matrix multiplication is always an important research topic. A joint study by researchers at Harvard University and MIT set the record for the fastest matrix multiplication.

From Quantamagazine by Kevin Hartnett, Heart of the Machine compiled, edited by Canoe, Dimensions.

As a basic mathematical operation, matrix multiplication is widely used in the field of computer science. The fast algorithm of matrix multiplication is of great significance to scientific calculation. Beginning with Strassen’s algorithm in 1969, people became aware of the existence of fast algorithms and began decades of exploration and research.

When you have two matrices of the same size, you can multiply them to get a third matrix. For example, the product of a pair of 2-by-2 matrices will also be a 2-by-2 matrix, containing four elements. So the product of two n by n matrices is another N by n matrix with n^2 elements.

Therefore, matrix multiplication requires at least n^2 steps, and the desired computational complexity is O(n^2).

In October 2020, two researchers from Harvard University and MIT published a paper that created the fastest algorithm ever for matrix multiplication, with a computational complexity 100,000 times less than the previous fastest algorithm. Among them, Josh Alman, the first author of the paper, is a postdoctoral student at Harvard University, mainly studying algorithm design and complexity theory. Vassilevska Williams is an associate professor at MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL), where she applies combinatorial and graph theory tools to computing.

Photo (left) Josh Alman; Photo (right) Virginia Vassilevska Williams.

Address: arxiv.org/pdf/2010.05…

Operation method of matrix multiplication

To understand this process and how to improve it, let’s first look at A pair of 2 x 2 matrices, matrix A and matrix B. To compute their product, you need to use the corresponding rows of matrix A and the corresponding columns of matrix B. The specific operation method is shown in the figure below:

The above operation is called the inner product of the matrix, and the values of the other elements in the product matrix can be calculated using the method shown above. In the case above, such a method requires eight multiplications and some addition. In general, when you multiply two n x n matrices, it takes n^3 multiplications.

As matrices grow, the number of multiplication operations required for matrix multiplication grows much faster than for addition. Usually, researchers measure the speed of matrix multiplication only by the number of multiplications required.

For centuries, people thought that n^3 was the fastest way to do matrix multiplication. Strassen proposed a complex set of relationships, thus replacing one of the eight multiplications mentioned above with 14 additions.

In 1981, Arnold Schonhage used this method to prove that the computational complexity of matrix multiplication can be reduced to O(n^2.522), and Strassen later called this method the Laser method.

Set a new record

For decades, every improvement in the speed of matrix multiplication has been due to improvements in laser methods, as researchers have found efficient ways to switch between the two types of problems. So does the new approach of Alman and Vassilevska Williams.

In matrix multiplication, the computational complexity of two N x n matrices can be used

Represents, wherein

The previous record was set in 2014 by Francois Le Gall, which included:

And in Alman and Vassilevska Williams’ new method:

Specifically, they reduced the complexity to O(n^2.3728596), setting a new record for the fastest matrix multiplication.

Notably, Vassilevska Williams reduced this figure to N ^2.372873 in 2012, but it was shattered by Francois Le Gall’s N ^2.3728639 in 2014.

However, although this method has brought some improvement in the speed of matrix multiplication, it can be seen that the improvement is getting smaller and smaller.

Francois Le Gall, Associate Professor, Graduate School of Mathematics, Nagoya University, Japan.

In fact, Alman and Vassilevska Williams’ improvements may have reached the limits of the laser method, but they still fall far short of the ultimate theoretical goal.

“It is not possible to get down to O(n^2) complexity using the method in this study,” said Chris Umans, a computer science professor at Caltech. To do that, new ways need to be found.

Interested readers can read the original paper for more details on the improvements.

The original link: www.quantamagazine.org/mathematici…