www.quantamagazine.org
Open in
urlscan Pro
2606:4700::6812:ce
Public Scan
Submitted URL: https://news.join1440.com/t/j-l-skiyun-duukljdjtl-jy/
Effective URL: https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/?utm_source=join1440&utm_...
Submission: On March 11 via manual from FR — Scanned from FR
Effective URL: https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/?utm_source=join1440&utm_...
Submission: On March 11 via manual from FR — Scanned from FR
Form analysis
5 forms found in the DOMPOST https://quantamagazine.us1.list-manage.com/subscribe/post?u=0d6ddf7dc1a0b7297c8e06618&id=f0cb61321c
<form action="https://quantamagazine.us1.list-manage.com/subscribe/post?u=0d6ddf7dc1a0b7297c8e06618&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