www.quantamagazine.org Open in urlscan Pro
2606:4700::6812:ce  Public Scan

Form analysis
5 forms found in the DOM

POST https://quantamagazine.us1.list-manage.com/subscribe/post?u=0d6ddf7dc1a0b7297c8e06618&id=f0cb61321c

<form action="https://quantamagazine.us1.list-manage.com/subscribe/post?u=0d6ddf7dc1a0b7297c8e06618&amp;id=f0cb61321c" target="_blank" method="post" class="bg-white">
  <div class="newsletter__form__inner flex flex-items-start mha">
    <div class="newsletter__form__field flex flex-auto relative fill-v"><label class="screen-reader-text" for="newsletter-email">Email</label><input type="email" class="flex fill-h px1 input--transparent pangram light scale3" name="EMAIL"
        id="newsletter-email" placeholder="Email address" autocorrect="off" autocapitalize="off"></div><button type="submit" class="ph2 pangram scale5 medium fill-v orange hover--black">Subscribe</button>
  </div>
</form>

---

<form>
  <div class="input-container"><input type="email" name="login_email" id="login_email" value="" class=""><label for="login_email" data-label="email">email</label></div>
  <div class="input-container"><input type="password" name="login_password" id="login_password" value="" class=""><label for="login_password" data-label="password">password</label></div>
  <div class="checkbox-container undefined"><input type="checkbox" value="login_remember" id="login_remember" name="login_remember" readonly=""><i class="psuedo-checkbox"></i><label for="login_remember">Remember me</label></div>
  <div class="login-modal__submit"><input type="submit" class="button login__submit orange mr1" value="Log in" disabled="">
    <p class="theme__accent link scale5 pangram inline medium color-transition hover--black"><span class="no-wrap" aria-haspopup="dialog">Forgot your password ?</span><svg class="ml05 icon icon-offset" viewBox="0 0 50 50"
        enable-background="new 0 0 50 50">
        <path fill="currentColor" d="M50 25l-17.4-8.7v6.5H0v4.4h32.6v6.5"></path>
      </svg></p>
  </div>
</form>

---

<form>
  <div class="input-container"><input type="first_name" name="sign_up_first_name" id="sign_up_first_name" value="" class=""><label for="sign_up_first_name" data-label="First Name">First Name</label></div>
  <div class="input-container"><input type="last_name" name="sign_up_last_name" id="sign_up_last_name" value="" class=""><label for="sign_up_last_name" data-label="Last Name">Last Name</label></div>
  <div class="input-container"><input type="email" name="sign_up_email" id="sign_up_email" value="" class=""><label for="sign_up_email" data-label="email">email</label></div>
  <div class="input-container"><input type="password" name="sign_up_password" id="sign_up_password" value="" class=""><label for="sign_up_password" data-label="password">password</label></div>
  <div class="input-container"><input type="password" name="sign_up_password_verify" id="sign_up_password_verify" value="" class=""><label for="sign_up_password_verify" data-label="Retype password">Retype password</label></div>
  <div class="align-c pv1"><input type="submit" class="button login__submit orange mr1" value="Create an account" disabled=""></div>
</form>

---

<form>
  <div class="input-container"><input type="email" name="forgot_password_email" id="forgot_password_email" value="" class=""><label for="forgot_password_email" data-label="email">email</label></div><input type="submit"
    class="login__submit button orange" value="Send" disabled="">
</form>

---

<form>
  <div class="input-container"><input type="password" name="new_password" id="new_password" value="" class=""><label for="new_password" data-label="Password">Password</label></div>
  <div class="input-container"><input type="password" name="new_password_verify" id="new_password_verify" value="" class=""><label for="new_password_verify" data-label="Retype new password">Retype new password</label></div><input type="submit"
    class="login__submit button orange" value="Send" disabled="">
</form>

---

Text Content

We care about your data, and we'd like to use cookies to give you a smooth
browsing experience. Please agree and read more about our privacy policy.Agree
Quanta Homepage

 * Physics
 * Mathematics
 * Biology
 * Computer Science
 * Topics
 * Archive

 * Saved articles
 * Login
 * Search
 * 






New Breakthrough Brings Matrix Multiplication Closer to Ideal
Comment
4
Save Article
Read Later

SHARE


Facebook

Twitter
Copied!

Copy link

Email

Pocket

Reddit

Ycombinator

Flipboard


 * Comment
   4
   Comments
 * Save Article
   Read Later
   Read Later


algorithms


NEW BREAKTHROUGH BRINGS MATRIX MULTIPLICATION CLOSER TO IDEAL

By Steve Nadis

March 7, 2024

By eliminating a hidden inefficiency, computer scientists have come up with a
new way to multiply large matrices that’s faster than ever.
Comment
4
Save Article
Read Later


Merrill Sherman/Quanta Magazine

By Steve Nadis

Contributing Writer

--------------------------------------------------------------------------------

March 7, 2024

--------------------------------------------------------------------------------

View PDF/Print Mode
algorithmscomputer sciencelinear algebramathematicsmultiplicationAll topics



INTRODUCTION

Computer scientists are a demanding bunch. For them, it’s not enough to get the
right answer to a problem — the goal, almost always, is to get the answer as
efficiently as possible.

Take the act of multiplying matrices, or arrays of numbers. In 1812, the French
mathematician Jacques Philippe Marie Binet came up with the basic set of rules
we still teach students. It works perfectly well, but other mathematicians have
found ways to simplify and speed up the process. Now the task of hastening the
process of matrix multiplication lies at the intersection of mathematics and
computer science, where researchers continue to improve the process to this day
— though in recent decades the gains have been fairly modest. Since 1987,
numerical improvements in matrix multiplication have been “small and … extremely
difficult to obtain,” said François Le Gall, a computer scientist at Nagoya
University.

Now, three researchers — Ran Duan and Renfei Zhou of Tsinghua University and
Hongxun Wu of the University of California, Berkeley — have taken a major step
forward in attacking this perennial problem. Their new results, presented last
November at the Foundations of Computer Science conference, stem from an
unexpected new technique, Le Gall said. Although the improvement itself was
relatively small, Le Gall called it “conceptually larger than other previous
ones.”

The technique reveals a previously unknown and hence untapped source of
potential improvements, and it has already borne fruit: A second paper,
published in January, builds upon the first to show how matrix multiplication
can be boosted even further.

Share this article

Facebook

Twitter
Copied!

Copy link

Email

Pocket

Reddit

Ycombinator

Flipboard


--------------------------------------------------------------------------------

Newsletter

Get Quanta Magazine delivered to your inbox

Subscribe now
Recent newsletters


Renfei Zhou helped find a new method to multiply matrices faster than ever
before.

Wei Yu


INTRODUCTION

“This is a major technical breakthrough,” said William Kuszmaul, a theoretical
computer scientist at Harvard University. “It is the biggest improvement in
matrix multiplication we’ve seen in more than a decade.”


ENTER THE MATRIX

It may seem like an obscure problem, but matrix multiplication is a fundamental
computational operation. It’s incorporated into a large proportion of the
algorithms people use every day for a variety of tasks, from displaying sharper
computer graphics to solving logistical problems in network theory. And as in
other areas of computation, speed is paramount. Even slight improvements could
eventually lead to significant savings of time, computational power and money.
But for now, theoreticians are mainly interested in figuring out how fast the
process can ever be.

The traditional way of multiplying two n-by-n matrices — by multiplying numbers
from each row in the first matrix by numbers in the columns in the second —
requires n3 separate multiplications. For 2-by-2 matrices, that means 23 or 8
multiplications.

Merrill Sherman/Quanta Magazine

In 1969, the mathematician Volker Strassen revealed a more complicated procedure
that could multiply 2-by-2 matrices in just seven multiplicative steps and 18
additions. Two years later, the computer scientist Shmuel Winograd demonstrated
that seven is, indeed, the absolute minimum for 2-by-2 matrices.

Merrill Sherman/Quanta Magazine

Strassen exploited that same idea to show that all larger n-by-n matrices can
also be multiplied in fewer than n3 steps. A key element in this strategy
involves a procedure called decomposition — breaking down a large matrix into
successively smaller submatrices, which might end up being as small as 2-by-2 or
even 1-by-1 (these are just single numbers).

The rationale for dividing a giant array into tiny pieces is pretty simple,
according to Virginia Vassilevska Williams, a computer scientist at the
Massachusetts Institute of Technology and co-author of one of the new papers.
“It’s hard for a human to look at a large matrix (say, on the order of
100-by-100) and think of the best possible algorithm,” Vassilevska Williams
said. Even 3-by-3 matrices haven’t been fully solved yet. “Nevertheless, one can
use a fast algorithm that one has already developed for small matrices to also
obtain a fast algorithm for larger matrices.”

The key to speed, researchers have determined, is to reduce the number of
multiplication steps, lowering that exponent from n3 (for the standard method)
as much as they can. The lowest possible value, n2, is basically as long as it
takes just to write the answer. Computer scientists refer to that exponent as
omega, ω, with nω being the fewest possible steps needed to successfully
multiply two n-by-n matrices as n grows very large. “The point of this work,”
said Zhou, who also co-authored the January 2024 paper, “is to see how close to
2 you can come, and whether it can be achieved in theory.”


INTRODUCTION


A LASER FOCUS

In 1986, Strassen had another big breakthrough when he introduced what’s called
the laser method for matrix multiplication. Strassen used it to establish an
upper value for omega of 2.48. While the method is only one step in large matrix
multiplications, it’s one of the most important because researchers have
continued to improve upon it.

One year later, Winograd and Don Coppersmith introduced a new algorithm that
beautifully complemented the laser method. This combination of tools has
featured in virtually all subsequent efforts to speed up matrix multiplication.

Here’s a simplified way of thinking about how these different elements fit
together. Let’s start with two large matrices, A and B, that you want to
multiply together. First, you decompose them into many smaller submatrices, or
blocks, as they’re sometimes called. Next, you can use Coppersmith and
Winograd’s algorithm to serve as a kind of instruction manual for handling, and
ultimately assembling, the blocks. “It tells me what to multiply and what to add
and what entries go where” in the product matrix C, Vassilevska Williams said.
“It’s just a recipe to build up C from A and B.”

There is a catch, however: You sometimes end up with blocks that have entries in
common. Leaving these in the product would be akin to counting those entries
twice, so at some point you need to get rid of those duplicated terms, called
overlaps. Researchers do this by “killing” the blocks they’re in — setting their
components equal to zero to remove them from the calculation.



Virginia Vassilevska Williams was part of a team that improved upon the new
approach to multiply matrices, coming up with the current fastest approach.

Jared Charney


INTRODUCTION

That’s where Strassen’s laser method finally comes into play. “The laser method
typically works very well and generally finds a good way to kill a subset of
blocks to remove the overlap,” Le Gall said. After the laser has eliminated, or
“burned away,” all the overlaps, you can construct the final product matrix, C.

Putting these various techniques together results in an algorithm for
multiplying two matrices with a deliberately stingy number of multiplications
overall — at least in theory. The laser method is not intended to be practical;
it’s just a way to think about the ideal way to multiply matrices. “We never run
the method [on a computer],” Zhou said. “We analyze it.”

And that analysis is what led to the biggest improvement to omega in more than a
decade.


A LOSS IS FOUND

Last summer’s paper, by Duan, Zhou and Wu, showed that Strassen’s process could
still be sped up significantly. It was all because of a concept they called a
hidden loss, buried deep within previous analyses — “a result of unintentionally
killing too many blocks,” Zhou said.

The laser method works by labeling blocks with overlaps as garbage, slated for
disposal; other blocks are deemed worthy and will be saved. The selection
process, however, is somewhat randomized. A block rated as garbage may, in fact,
turn out to be useful after all. This wasn’t a total surprise, but by examining
many of these random choices, Duan’s team determined that the laser method was
systematically undervaluing blocks: More blocks should be saved and fewer thrown
out. And, as is usually the case, less waste translates into greater efficiency.

“Being able to keep more blocks without overlap thus leads to … a faster matrix
multiplication algorithm,” Le Gall said.

After proving the existence of this loss, Duan’s team modified the way that the
laser method labeled blocks, reducing the waste substantially. As a result, they
set a new upper bound for omega at around 2.371866 — an improvement over the
previous upper bound of 2.3728596, set in 2020 by Josh Alman and Vassilevska
Williams. That may seem like a modest change, lowering the bound by just about
0.001. But it’s the single biggest improvement scientists have seen since 2010.
Vassilevska Williams and Alman’s 2020 result, by comparison, only improved upon
its predecessor by 0.00001.

But what’s most exciting for researchers isn’t just the new record itself —
which didn’t last long. It’s also the fact that the paper revealed a new avenue
for improvement that, until then, had gone totally unnoticed. For nearly four
decades, everyone has been relying upon the same laser method, Le Gall said.
“Then they found that, well, we can do better.”


RELATED:

--------------------------------------------------------------------------------


 1. MATRIX MULTIPLICATION INCHES CLOSER TO MYTHIC GOAL


 2. AI REVEALS NEW POSSIBILITIES IN MATRIX MULTIPLICATION


 3. SCIENTISTS FIND OPTIMAL BALANCE OF DATA STORAGE AND TIME


 4. RESEARCHERS APPROACH NEW SPEED LIMIT FOR SEMINAL PROBLEM

The January 2024 paper refined this new approach, enabling Vassilevska Williams,
Zhou and their co-authors to further reduce the hidden loss. This led to an
additional improvement of omega’s upper bound, reducing it to 2.371552. The
authors also generalized that same technique to improve the multiplication
process for rectangular (n-by-m) matrices — a procedure that has applications in
graph theory, machine learning and other areas.

Some further progress along these lines is all but certain, but there are
limits. In 2015, Le Gall and two collaborators proved that the current approach
— the laser method coupled with the Coppersmith-Winograd recipe — cannot yield
an omega below 2.3078. To make any further improvements, Le Gall said, “you need
to improve upon the original [approach] of Coppersmith and Winograd that has not
really changed since 1987.” But so far, nobody has come up with a better way.
There may not even be one.

“Improving omega is actually part of understanding this problem,” Zhou said. “If
we can understand the problem well, then we can design better algorithms for it.
[And] people are still in the very early stages of understanding this age-old
problem.”


By Steve Nadis

Contributing Writer

--------------------------------------------------------------------------------

March 7, 2024

--------------------------------------------------------------------------------

View PDF/Print Mode
algorithmscomputer sciencelinear algebramathematicsmultiplicationAll topics

Share this article

Facebook

Twitter
Copied!

Copy link

Email

Pocket

Reddit

Ycombinator

Flipboard


--------------------------------------------------------------------------------

Newsletter

Get Quanta Magazine delivered to your inbox

Subscribe now
Recent newsletters
The Quanta Newsletter

Get highlights of the most important news delivered to your email inbox

Email
Subscribe
Recent newsletters



ALSO IN COMPUTER SCIENCE

natural language processing


HOW SELECTIVE FORGETTING CAN HELP AI LEARN BETTER

By Amos Zeeberg
February 28, 2024
Comment
4
Save Article
Read Later

quantum information theory


NEVER-REPEATING TILES CAN SAFEGUARD QUANTUM INFORMATION

By Ben Brubaker
February 23, 2024
Comment
4
Save Article
Read Later

artificial intelligence


HOW QUICKLY DO LARGE LANGUAGE MODELS LEARN UNEXPECTED SKILLS?

By Stephen Ornes
February 13, 2024
Comment
9
Save Article
Read Later



COMMENT ON THIS ARTICLE

Quanta Magazine moderates comments to facilitate an informed, substantive, civil
conversation. Abusive, profane, self-promotional, misleading, incoherent or
off-topic comments will be rejected. Moderators are staffed during regular
business hours (New York time) and can only accept comments written in English. 


Show comments


NEXT ARTICLE

Cellular Self-Destruction May Be Ancient. But Why?
Quanta Homepage

Facebook

Twitter

Youtube

Instagram
 * About Quanta
 * Archive
 * Contact Us
 * Terms & Conditions
 * Privacy Policy

--------------------------------------------------------------------------------

All Rights Reserved © 2024
An editorially independent publication supported by the Simons Foundation.
Close
Log in to Quanta


USE YOUR SOCIAL NETWORK

FacebookConnect with Facebook
Connect with Google
or
email
password
Remember me

Forgot your password ?

Don't have an account yet? Sign up
Close
Sign Up
First Name
Last Name
email
password
Retype password

Creating an account means you accept Quanta Magazine's
Terms & Conditions and Privacy Policy
Close
Forgot your password?

We’ll email you instructions to reset your password

email
Close
Change your password

Enter your new password

Password
Retype new password
Close