Matrix Multiplication Inches Closer to Mythic Goal

Jul 12, 2021 | Location West County

Matrix Multiplication Inches Closer to Mythic Goal

A recent paper set the fastest record for multiplying two matrices. But it also marks the end of the line for a method researchers have relied on for decades to make improvements.

A graphic showing improvements in the speed of matrix multiplication

Mathematicians have been getting closer to their goal of reaching exponent two — meaning multiplying a pair of n-by-n matrices in only n2 steps — but will they ever reach it?

Kevin Hartnett

Senior Writer/Editor

March 23, 2021

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 nsteps — 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.

A paper posted in October comes the closest yet, describing the fastest-ever method for multiplying two matrices together. The result, by Josh Alman, a postdoctoral researcher at Harvard University, and Virginia Vassilevska Williams of the Massachusetts Institute of Technology, shaves about one-hundred-thousandth off the exponent of the previous best mark. It’s typical of the recent painstaking gains in the field.

To get a sense for this process, and how it can be improved, let’s start with a pair of two-by-two matrices, A and B. When computing each entry of their product, you use the corresponding row of A and corresponding column of B. So to get the top-right entry, multiply the first number in the first row of A by the first number in the second column of B, then multiply the second number in the first row of A by the second number in the second column of B, and add those two products together.

A graphic showing some of the steps involved in multiplying matrices

Samuel Velasco/Quanta Magazine

This operation is known as taking the “inner product” of a row with a column. To compute the other entries in the product matrix, repeat the procedure with the corresponding rows and columns.

Altogether, the textbook method for multiplying two-by-two matrices requires eight multiplications, plus some additions. Generally, this way of multiplying two n-by-n matrices together requires n3 multiplications along the way.

A graphic showing how to multiply matrices, and how many steps it takes

As matrices grow larger, the number of multiplications needed to find their product increases much faster than the number of additions. While it takes eight intermediate multiplications to find the product of two-by-two matrices, it takes 64 to find the product of four-by-four matrices. However, the number of additions required to add those sets of matrices is much closer together. Generally, the number of additions is equal to the number of entries in the matrix, so four for the two-by-two matrices and 16 for the four-by-four matrices. This difference between addition and multiplication begins to get at why researchers measure the speed of matrix multiplication purely in terms of the number of multiplications required.

“Multiplications are everything,” said Umans. “The exponent on the eventual running time is fully dependent only on the number of multiplications. The additions sort of disappear.”

For centuries people thought n3 was simply the fastest that matrix multiplication could be done. In 1969, Volker Strassen reportedly set out to prove that there was no way to multiply two-by-two matrices using fewer than eight multiplications. Apparently he couldn’t find the proof, and after a while he realized why: There’s actually a way to do it with seven!

Strassen came up with a complicated set of relationships that made it possible to replace one of those eight multiplications with 14 extra additions. That might not seem like much of a difference, but it pays off thanks to the importance of multiplication over addition. And by finding a way to save a single multiplication for small two-by-two matrices, Strassen found an opening that he could exploit when multiplying larger matrices.

“This tiny improvement leads to huge improvements with big matrices,” Vassilevska Williams said.

Say, for example, you want to multiply a pair of eight-by-eight matrices. One way to do it is to break each big matrix into four four-by-four matrices, so each one has four entries. Because a matrix can also have entries that are themselves matrices, you can thus think of the original matrices as a pair of two-by-two matrices, each of whose four entries is itself a four-by-four matrix. Through some manipulation, these four-by-four matrices can themselves each be broken into four two-by-two matrices.

The point of this reduction — of repeatedly breaking bigger matrices into smaller matrices — is that it’s possible to apply Strassen’s algorithm over and over again to the smaller matrices, reaping the savings of his method at each step. Altogether, Strassen’s algorithm improved the speed of matrix multiplication from n3 to n2.81 multiplicative steps.

The next big improvement took place in the late 1970s, with a fundamentally new way to approach the problem. It involves translating matrix multiplication into a different computational problem in linear algebra involving objects called tensors. The particular tensors used in this problem are three-dimensional arrays of numbers composed of many different parts, each of which looks like a small matrix multiplication problem.

Matrix multiplication and this problem involving tensors are equivalent to each other in a sense, yet researchers already had faster procedures for solving the latter one. This left them with the task of determining the exchange rate between the two: How big are the matrices you can multiply for the same computational cost that it takes to solve the tensor problem?

“This is a very common paradigm in theoretical computer science, of reducing between problems to show they’re as easy or as hard as each other,” Alman said.

In 1981 Arnold Schönhage used this approach to prove that it’s possible to perform matrix multiplication in n2.522 steps. Strassen later called this approach the “laser method.”

Over the last few decades, every improvement in matrix multiplication has come from improvements in the laser method, as researchers have found increasingly efficient ways to translate between the two problems. In their new proof, Alman and Vassilevska Williams reduce the friction between the two problems and show that it’s possible to “buy” more matrix multiplication than previously realized for solving a tensor problem of a given size.

“Josh and Virginia have basically found a way of taking the machinery inside the laser method and tweaking it to get even better results,” said Henry Cohn of Microsoft Research.

The paper improves the theoretical speed limit on matrix multiplication to n2.3728596.

It also allows Vassilevska Williams to regain the matrix multiplication crown, which she previously held in 2012 (n2.372873), then lost in 2014 to François Le Gall (n2.3728639).

Yet for all the jockeying, it’s also clear this approach is providing diminishing returns. In fact, Alman and Vassilevska Williams’s improvement may have nearly maxed out the laser method — remaining far short of that ultimate theoretical goal.

“There isn’t likely to be a leap to exponent two using this particular family of methods,” Umans said.

Getting there will require discovering new methods and sustaining the belief that it’s even possible.

Vassilevska Williams remembers a conversation she once had with Strassen about this: “I asked him if he thinks you can get [exponent 2] for matrix multiplication and he said, ‘no, no, no, no, no.’”

 

 

 

 

 

 

 

 
Locations near
ME
Ashburn 0.93 mi
43330 Junction Plaza
#160
Ashburn, VA 20147
Sterling 4.07 mi
44 Pidgeon Hill Drive
#100
Sterling, VA 20165
Leesburg 5.69 mi
521 E Market St
#B
Leesburg, VA 20176
Herndon 7.66 mi
2465 Centreville Road
#J2
Herndon, VA 20171
Stone Ridge 7.88 mi
42020 Village Center Plaza
#100
Stone Ridge, VA 20105
Reston 8.62 mi
1424 North Point Village Center
Reston, VA 20194
Purcellville 12.72 mi
1020 E Main St
Ste L
Purcellville, VA 20132
North Potomac 13.58 mi
12150 Darnestown Rd
Gaithersburg, MD 20878
Centreville 14.52 mi
5959 Centreville Crest Ln
Centreville, VA 20121
Fairfax 14.67 mi
11891 Grand Commons Ave
Fairfax, VA 22030
Potomac 14.98 mi
10232 River Road
#B
Potomac, MD 20854
Germantown MD 15.03 mi
12800 Middlebrook Road
Germantown, MD 20874
Tysons 15.45 mi
328 Maple Ave E
#A
Vienna, VA 22180
Haymarket 17.87 mi
15125 Washington St
Haymarket, VA 20169
Rockville 18.19 mi
20 Courthouse Square
#106
Rockville, MD 20850
Mclean 18.23 mi
1320 Old Chain Bridge Road
Suite #190
McLean, VA 22101
Gaithersburg 18.71 mi
9132 Rothbury Drive
Gaithersburg, MD 20886
North Bethesda 20.42 mi
5268 Nicholson Ln
#N
Kensington, MD 20895
Falls Church 20.59 mi
6674 Arlington Blvd
Falls Church, VA 22042
Manassas 20.65 mi
9722 Liberia Ave
Manassas, VA 20110
Bristow 20.71 mi
12705 Braemar Village Pz
Bristow, VA 20136
Burke 20.82 mi
9411 Old Burke Lake Rd
#C
Burke, VA 22015
Bethesda 21.3 mi
4918 Fairmont Ave
Bethesda, MD 20814
Annandale 21.64 mi
7000 Columbia Pike
Annandale, VA 22003
Damascus 22.77 mi
9815 Main St
Damascus, MD 20872
Arlington, VA 23.29 mi
4801 1st St N
Arlington, VA 22203
Cathedral Heights 23.51 mi
3706 Macomb St NW
Washington, D.C., DC 20016
Olney 23.96 mi
18157 Village Center Dr
Olney, MD 20832
Downtown Silver Spring 24.94 mi
1133 East West Highway
Silver Spring, MD 20910
Lorton 25.06 mi
9027 Silverbrook Rd
#A
Fairfax Station, VA 22039
West Washington 25.69 mi

Washington, DC 20009
Alexandria City 25.7 mi
4605 Duke Street
Alexandria, VA 22304
Lake Ridge 26.5 mi
12473 Dillingham Square
Lake Ridge, VA 22192
Frederick North 26.7 mi
905 W. 7th Street
Frederick, MD 21701
Northern Silver Spring 26.75 mi
732 Cloverly Street
Silver Spring, MD 20905
Alexandria 27.17 mi
6483 Old Beulah Street
Alexandria, VA 22315
Warrenton 27.42 mi
512 Fletcher Drive
Warrenton, VA 20186
Mount Airy 28.24 mi
411 E Ridgeville Blvd
Mt Airy, MD 21771
Capitol Hill DC 28.48 mi
621 Pennsylvania Ave SE
1st-floor unit
Washington, DC 20003
Dale City 28.99 mi
5512 Staples Mill Plaza
Dale City, VA 22193
Mount Vernon 29.66 mi
7696 H Richmond Hwy
Alexandria, VA 22306
Beltsville 30.89 mi
10914 Baltimore Ave
#B
Beltsville, MD 20705
Clarksville 31.56 mi
12250 Clarksville Pike
#D
Clarksville, MD 21029
Laurel 35.02 mi
10095 Washington Blvd N
#136
Laurel, MD 20723
Woodmore 35.27 mi
9101 Woodmore Centre Drive
Lanham, MD 20706
Glenn Dale 35.83 mi
10559 Greenbelt Rd
Lanham, MD 20706
Sykesville 36.57 mi
1207 Liberty Rd.
#D-104
Sykesville, MD 21784
Ellicott City 37.11 mi
3290 Pine Orchard Lane
#B
Ellicott City, MD 21042
Winchester 37.62 mi
2512 S Pleasant Valley Rd
Winchester, VA 22601
Columbia 38.19 mi
8827 Centre Park Drive
#F
Columbia, MD 21045
Stafford 39.58 mi
263 Garrisonville Road
#104
Stafford, VA 22554
Bowie 41.26 mi
15231 Hall Rd
Bowie, MD 20721
Waldorf 42.24 mi
3022 Festival Way
Waldorf, MD 20601
Crofton 42.6 mi
1153 Route 3 North
#120
Crofton, MD 21054
Owings Mills 44.15 mi
9433 Common Brook Rd #100
Owings Mills, MD 21117
Pikesville 46.84 mi
1433 Reisterstown Rd
Pikesville, MD 21208
Dunkirk 49.92 mi
10735 Town Center Blvd
#7
Dunkirk, MD 20754