Communications of the ACM
Matrix Multiplication Inches Closer to Mythic Goal
A paper posted in October describes the fastest-ever method for multiplying two matrices together.
Credit: Samuel Velasco/Quanta Magazine
For computer scientists and mathematicians, opinions about "exponent two" boil down to a sense of how the world should be.
"It's hard to distinguish scientific thinking from wishful thinking," said Chris Umans of the California Institute of Technology. "I want the exponent to be two because it's beautiful."
"Exponent two" refers to the ideal speed — in terms of number of steps required — of performing one of the most fundamental operations in math: matrix multiplication. If exponent two is achievable, then it's possible to carry out matrix multiplication as fast as physically possible. If it's not, then we're stuck in a world misfit to our dreams.
Matrices are arrays of numbers. When you have two matrices of compatible sizes, it's possible to multiply them to produce a third matrix. For example, if you start with a pair of two-by-two matrices, their product will also be a two-by-two matrix, containing four entries. More generally, the product of a pair of n-by-n matrices is another n-by-n matrix with n2 entries.
For this reason, the fastest one could possibly hope to multiply pairs of matrices is in n2 steps — that is, in the number of steps it takes merely to write down the answer. This is where "exponent two" comes from.
And while no one knows for sure whether it can be reached, researchers continue to make progress in that direction.
From Quanta magazine
View Full Article
No entries found