How AI Discovered a Faster Matrix Multiplication Algorithm

Summary

The enigmatic operation of matrix multiplication, fundamental in fields from computer graphics to quantum physics, has been revolutionized by a breakthrough from Google's AI research lab, DeepMind. Traditionally, matrix multiplication involves a complex and time-consuming process, with the standard algorithm requiring a cubic number of steps relative to the matrix size. However, DeepMind's AlphaTensor, an AI built on reinforcement learning, has discovered a new algorithm that significantly reduces the number of multiplication steps needed, particularly for matrices with binary elements. This achievement not only breaks a 50-year-old record but also exemplifies the potential for AI to augment human intelligence, as mathematicians have already built upon AlphaTensor's findings to further optimize matrix multiplication methods.

Takeaways

• 🧮 **Matrix Multiplication Importance**: Matrix multiplication is a fundamental operation in mathematics, crucial for fields like computer graphics, neural networks, and quantum physics.
• 🚀 **Efficiency Challenge**: Finding more efficient matrix multiplication methods is a significant challenge due to its complexity, which impacts the ability to solve larger problems in a reasonable time.
• 📚 **Standard Algorithm**: The traditional method for multiplying matrices involves a straightforward process but requires N-cubed steps, which becomes inefficient for large matrices.
• 🔍 **Strassen's Algorithm**: Volker Strassen's algorithm reduces the number of multiplication steps from eight to seven for 2x2 matrices, offering substantial computational savings for larger matrices.
• 🏆 **Winograd's Proof**: Shmuel Winograd proved that no algorithm could multiply two 2x2 matrices using six or fewer multiplications, establishing Strassen's algorithm as the best solution for a long time.
• 🤖 **DeepMind's Breakthrough**: Google's DeepMind AI lab discovered a new algorithm that surpasses Strassen's method for multiplying 4x4 matrices with binary elements, setting a new record.
• 🤹 **AlphaTensor**: DeepMind's AlphaTensor uses reinforcement learning, derived from the AlphaGo algorithm, to find more efficient matrix multiplication algorithms by playing a 'game' of minimizing multiplication steps.
• 🧠 **Reinforcement Learning**: AlphaTensor learns through strategic penalties and rewards, optimizing its approach to achieve the task of finding the most efficient matrix multiplication algorithms.
• 🧩 **Tensor Decomposition**: The process of breaking down a 3D tensor into rank-1 tensors represents each step in a matrix multiplication algorithm, with fewer tensors correlating to fewer multiplication steps.
• 🔬 **Pattern Discovery**: AlphaTensor's training led to the discovery of patterns for efficient tensor decomposition, which not only rediscovered Strassen's algorithm but also surpassed it.
• 🤝 **Human-AI Collaboration**: The collaboration between AI programs like AlphaTensor and mathematicians can lead to new discoveries, with AI providing tools and insights to guide mathematicians.

Q & A

What is matrix multiplication and why is it significant?

Matrix multiplication is a fundamental operation in mathematics used in various fields such as computer graphics, neural networks, and quantum physics. It involves performing mathematical operations on a two-dimensional array of numbers. Its significance lies in its widespread application in engineering, physics, and computational processes, where efficiency in matrix multiplication can lead to solving larger and more complex problems in a reasonable time.

Why is finding more efficient ways to multiply matrices a challenge?

Finding more efficient matrix multiplication methods is challenging because as the size of the matrices increases, the number of operations required grows rapidly, leading to a significant increase in computation time. Traditional methods become unwieldy for large matrices, thus the need for algorithms that can reduce the number of steps required to multiply matrices together.

What is the standard method for multiplying two 2x2 matrices?

The standard method involves multiplying elements from the first row of matrix A with the first column of matrix B, then adding them to get the first element of matrix C. This process is repeated for each row and column, resulting in eight multiplication steps for two 2x2 matrices.

Who is Volker Strassen and what is his contribution to matrix multiplication?

Volker Strassen is a German mathematician known for his work in analyzing algorithms. In 1969, he discovered a new algorithm for multiplying two 2x2 matrices that requires only seven multiplication steps, which was a significant improvement over the standard eight-step method.

What is the significance of Strassen's algorithm for larger matrices?

Strassen's algorithm offers dramatic computational savings for larger matrices because it allows them to be broken down into smaller ones. This means that the savings in multiplication steps can propagate over and over as the matrices are nested, resulting in fewer overall multiplication steps compared to the standard algorithm.

What is the significance of the new algorithm discovered by DeepMind for multiplying four by four matrices?

The new algorithm discovered by DeepMind is significant because it allows for even faster multiplication of large matrices by breaking them down into four by four matrices instead of two by two matrices. This breakthrough could potentially lead to more efficient computations in various fields.

How does AlphaTensor, the AI developed by DeepMind, work?

AlphaTensor is built on a reinforcement learning algorithm called AlphaZero. It plays a 'game' where it is rewarded for using fewer unique rank-1 tensors to decompose a 3D tensor representing a matrix multiplication operation. This approach allows it to discover more efficient matrix multiplication algorithms.

What is the role of a tensor in the context of AlphaTensor?

A tensor is an array of numbers with any number of dimensions. In the context of AlphaTensor, the process of multiplying any two matrices of a given size can be described by a single unique 3D tensor. This tensor is used to represent and decompose the matrix multiplication operation, with each rank-1 tensor describing a multiplication step in the algorithm.

How does reinforcement learning play a role in AlphaTensor's discovery process?

Reinforcement learning is a technique that strategically penalizes and rewards an AI system as it experiments with different ways to achieve its given task. In AlphaTensor's case, it is rewarded for using fewer rank-1 tensors to decompose the 3D tensor, driving the program towards an optimal solution for matrix multiplication.

What is the potential impact of AI systems like AlphaTensor on the field of mathematics?

AI systems like AlphaTensor have the potential to assist mathematicians in discovering new results and guiding their intuition. They can handle large, complex computations that would be impractical for humans to perform. However, they are not expected to replace mathematicians but rather to serve as tools that empower mathematicians to achieve more.

How did the mathematical community respond to the results published by AlphaTensor?

The mathematical community responded positively to the results published by AlphaTensor. For instance, two mathematicians in Austria, Manuel Kauers and Jakob Moosbauer, used AlphaTensor's algorithm as inspiration to further optimize the process, demonstrating a successful collaboration between AI technology and mathematicians.

What is the current understanding of the collaboration between AI and mathematicians?

The current understanding is that AI and mathematicians can collaborate effectively, with AI providing tools and insights that can help mathematicians find new results and solve complex problems. This collaboration is seen as a frontier that is only now being fully explored, with the potential to empower people to do more in the field of mathematics.

Outlines

00:00

🧮 Matrix Multiplication: An Enigma Solved by AI

Matrix multiplication is a fundamental operation in mathematics, crucial for fields like computer graphics, neural networks, and quantum physics. Despite its simplicity, it remains a complex problem for mathematicians. Researchers have been seeking more efficient methods to multiply matrices, which can significantly impact the ability to solve larger problems. The traditional method involves a substantial number of steps, which becomes impractical for large matrices. Volker Strassen's algorithm, discovered in 1969, reduced the number of multiplication steps for 2x2 matrices, offering significant computational savings for larger matrices. However, a new breakthrough by Google's DeepMind in October 2022 presented an algorithm that surpasses Strassen's for multiplying 4x4 matrices with binary elements, demonstrating the potential of AI in advancing mathematical computation.

05:02

🤖 AlphaTensor: AI's Role in Mathematical Discovery

AlphaTensor, an AI developed by DeepMind, utilized reinforcement learning to tackle the challenge of finding more efficient matrix multiplication algorithms. The process involved treating the task as a game, where the AI was rewarded for using fewer steps to decompose a 3D tensor representing a matrix multiplication. This approach led to the discovery of new algorithms, including one that improved upon Strassen's method for 4x4 matrices with modulo-2 elements. The use of AI in mathematical research is not new, but the success of AlphaTensor highlights the potential for collaboration between AI and mathematicians. The AI's discoveries have already inspired human mathematicians to further refine these algorithms, indicating a future where AI serves as a tool to augment human intellect rather than replace it.

10:03

🚀 The Future of AI and Mathematical Research

The exploration of tensor decomposition by AlphaTensor led to the discovery of new, faster algorithms for matrix multiplication, including a record-breaking method for 4x4 matrices with binary elements. This achievement not only demonstrated the power of AI in mathematical research but also its capacity to inspire and assist human mathematicians. The collaboration between AI and mathematicians, as seen with the work of Manuel Kauers and Jakob Moosbauer who built upon AlphaTensor's findings, signifies a promising frontier in scientific advancement. The integration of AI tools is expected to empower mathematicians, enhancing their ability to explore complex problems and discover new solutions, rather than making them obsolete.

Keywords

💡Matrix multiplication

Matrix multiplication is a fundamental mathematical operation that involves combining two matrices to produce a third matrix. It is a key concept in the video as it is the central operation that researchers are trying to optimize for efficiency. The video discusses how matrix multiplication is used in various fields such as computer graphics, neural networks, and quantum physics, and how improving its efficiency can solve larger problems more quickly.

💡Efficiency

Efficiency in the context of the video refers to the speed and computational resources required to perform matrix multiplication. The pursuit of more efficient matrix multiplication methods is a major theme, as it can expand the scope of solvable problems by making larger computations feasible within a reasonable time frame.

💡Volker Strassen

Volker Strassen is a German mathematician who is highlighted in the video for his discovery of a new algorithm for multiplying two by two matrices, which requires only seven multiplication steps instead of the traditional eight. His algorithm is significant because it offers computational savings for larger matrices, making it a cornerstone in the field for over 50 years.

💡Strassen's algorithm

Strassen's algorithm is a method for matrix multiplication that reduces the number of multiplications needed to perform the operation. The video emphasizes its importance in the history of matrix multiplication as it was the most efficient known method for a long time. It is also the benchmark that the new algorithm from DeepMind's AlphaTensor aims to surpass.

💡DeepMind

DeepMind is Google's artificial intelligence research lab that is featured in the video for discovering a new matrix multiplication algorithm that surpasses Strassen's algorithm for specific cases. DeepMind is known for training AI systems to master games and for its significant contributions to AI research, making it a key player in the advancements discussed.

💡AlphaTensor

AlphaTensor is an algorithm descended from AlphaGo, developed by DeepMind, that uses reinforcement learning to discover more efficient ways of performing matrix multiplication. It is the AI system that led to the breakthrough in matrix multiplication efficiency, particularly for matrices with elements of zero or one.

💡Reinforcement learning

Reinforcement learning is a type of machine learning where an agent learns to make decisions by performing actions in an environment to maximize a reward. In the video, AlphaTensor uses reinforcement learning to experiment with different ways to achieve efficient matrix multiplication, which is likened to playing a game with strategic penalties and rewards.

💡Tensor decomposition

Tensor decomposition is a mathematical technique used to break down a tensor into simpler building blocks, known as rank-1 tensors. In the context of the video, this technique is applied to represent and optimize the process of matrix multiplication, where each rank-1 tensor corresponds to a multiplication step in an algorithm.

💡AlphaZero

AlphaZero is a reinforcement learning algorithm developed by DeepMind that is the basis for AlphaTensor. It is known for mastering games like chess and Go, and its underlying principles are used to tackle the complex problem of finding more efficient matrix multiplication algorithms.

💡Modulo-2

Modulo-2 is a mathematical operation used in the context of the video to describe a specific case of matrix multiplication where the elements are only zero or one. The new algorithm discovered by AlphaTensor is particularly effective in this scenario, breaking the longstanding record for matrix multiplication efficiency.

💡Collaboration between AI and mathematicians

The video discusses the collaborative potential between artificial intelligence, represented by programs like AlphaTensor, and human mathematicians. It highlights how AI can assist in discovering new mathematical insights, which can then be further developed and understood by mathematicians, leading to a synergy that empowers both fields.

Highlights

Matrix multiplication is a fundamental operation in mathematics with applications in computer graphics, neural networks, and quantum physics.

Efficient matrix multiplication methods are sought after for solving larger problems more quickly.

Standard matrix multiplication algorithms take N-cubed steps, which becomes unwieldy for large matrices.

Volker Strassen's algorithm reduces the number of multiplication steps from eight to seven for 2x2 matrices.

Strassen's algorithm provides computational savings for larger matrices by breaking them down into smaller ones.

Shmuel Winograd proved that no algorithm can use six or fewer multiplications for 2x2 matrices, making Strassen's algorithm optimal.

DeepMind's AI lab discovered a new algorithm that beats Strassen's for multiplying 4x4 matrices with binary elements.

The new algorithm allows for even faster multiplication by breaking matrices into 4x4 blocks instead of 2x2.

AlphaTensor, an AI developed by DeepMind, uses reinforcement learning to find more efficient matrix multiplication algorithms.

Reinforcement learning involves penalizing and rewarding an AI as it experiments with different methods to achieve a task.

AlphaTensor uses tensor decomposition to simplify the process of finding efficient multiplication algorithms.

The AI program can represent the entire standard matrix multiplication algorithm through the decomposition of a 3D tensor.

DeepMind constructed a single-player game for AlphaTensor to learn efficient matrix multiplication methods.

AlphaTensor's algorithm for 4x4 matrices with modulo-2 elements uses only 47 multiplications, breaking a 50-year record.

The discovery of new algorithms by AlphaTensor has inspired mathematicians to further refine and optimize these methods.

Manuel Kauers and Jakob Moosbauer used AlphaTensor's algorithm as a starting point to reduce the steps for 5x5 matrix multiplication.

The collaboration between AI technology and mathematicians is seen as a promising frontier for future advancements.

AI tools like AlphaTensor are not expected to replace mathematicians but rather to empower them to achieve more.

Transcripts

There is an enigmatic and powerful mathematical operation

at work inside everything from computer graphics

and neural networks, to quantum physics.

It's simple enough for high school students to grasp

yet so complex that even seasoned mathematicians haven't mastered it.

This operation is called matrix multiplication.

Matrix multiplication is a very fundamental operation in

mathematics that appears in many computations in engineering

and in physics.

A matrix is a two dimensional array of numbers on which you

can perform operations like addition and multiplication.

Researchers have long sought more efficient ways

to multiply matrices together.

So if you even just make that a little bit faster, larger

problems come into reach.

Where for now, we would say that's too big to

be computable in reasonable time.

However, actually finding faster matrix multiplication methods is

a huge challenge.

But thanks to a new tool, researchers have finally broken

a long standing matrix multiplication record,

one that's more than 50 years old.

What's their secret weapon?

Students of linear algebra are taught a method for multiplying

matrices based on a centuries old algorithm.

It goes like this.

Multiply elements from the first row of matrix A

and the first column of matrix B

and add them to get the first element of matrix C.

Then repeat for the first row of matrix A

and the second column of matrix B, and add them for the second element in matrix C.

And so on.

Multiplying two two by two matrices this way,

takes eight multiplication steps.

Multiplying any two N by N matrices with the standard algorithm takes N-cubed steps.

Which is why applying this method to pairs of larger

matrices quickly becomes unwieldy.

If you take a matrix that is twice as big, then you have to

have a computation time that is eight times more.

So you can imagine, if you doubled it a couple of times, then you take

eight times more a couple of times, and you will very soon

reach the limits of what a computer can do.

Enter Volker Strassen,

a German mathematician known for his work analyzing algorithms.

In 1969, he discovered a new algorithm to multiply two by two matrices

that requires only seven multiplication steps.

Going from eight down to seven multiplications may seem trivial,

and the new addition steps look more complicated.

But Strassen's algorithm offers dramatic computational savings for larger matrices.

That's because when multiplying large matrices, they can be broken down into smaller ones.

For example, an eight by eight matrix can reduce to a series of

nested two by two matrices.

So Strassen's savings applied to these smaller matrix multiplications propagate over and over.

Applying Strassen's to an eight by eight matrix results

in a third fewer multiplication steps compared to the standard algorithm.

For very large matrices, these savings vastly outweigh the computation costs of the extra additions.

A year after Strassen invented his algorithm, IBM researcher Shmuel Winograd

proved it was impossible to use six or fewer multiplications

to multiply two by two matrices,

thus also proving that Strassens, with its seven multiplications is the best solution.

For half a century the most efficient method known for

multiplying two matrices of any reasonable size was to break

them down and apply Strassen's algorithm.

That was until October 2022, a new algorithm was revealed that beat

Strassen's, specifically for multiplying two four by four matrices

where the elements are only zero or one.

This new algorithm made it possible to multiply large matrices even faster

by breaking them into four by four matrices instead of two by two's.

So who or what was behind This breakthrough?

This new algorithm was discovered by Google's

artificial intelligence research lab, DeepMind.

For more than a decade, DeepMind has garnered attention for training AI systems

to master a host of games, everything from Atari Pong to chess.

Then, in 2016, DeepMind's AlphaGo achieved what was considered impossible at the time,

it defeated the top ranked human Go player, Lee Sedol , in a best of five match.

This victory shattered the limited notion of what's possible for computers to achieve.

DeepMind then set its sights on a problem even more challenging than Go.

I was like very surprised that even for very small cases, we

don't even know what's the optimal way of doing matrix multiplication.

And at some point, we realized

that this is actually a very good fit for machine learning techniques

To tackle matrix multiplication. DeepMind started with an

algorithm descended from AlphaGo called AlphaTensor.

AlphaTensor is built on a reinforcement learning algorithm

called AlphaZero.

So what one needs to do is to go really beyond the AlphaZero reinforcement learning algorithm

and to tackle this huge search space and to develop techniques

to find this, these needles in a very, very large haystack.

AlphaTensor isn't the first computer program to assist with

mathematical research.

In 1976, two mathematicians proved what's called the Four Color Theorem using a computer.

The theorem states, you only need four colors to fill in any map so no

neighboring regions match.

The pair verified their proof by processing all 1936 required cases

requiring more than 1000 hours of computing time.

Back then the larger mathematical community

was not prepared to cede logical reasoning to a machine.

However, the field has since come a long way.

AlphaTensor was trained with a technique called

reinforcement learning, which is kind of like playing a game.

Reinforcement Learning strategically penalizes and rewards an AI system as it

experiments with different ways to achieve its given task,

driving the program towards an optimal solution.

But what kind of game should AlphaTensor play in search of more efficient

matrix multiplication algorithms?

This is where the term tensor in AlphaTensor comes into play.

A tensor is just an array of numbers with any number of dimensions.

Vectors are 1D tensors, and matrices are 2D tensors.

The process of multiplying any two matrices of a given size

can be described by a single unique 3D tensor.

For example, when multiplying any two, two by two matrices,

we can build the corresponding 3D tensor.

Each dimension of this cube represents one of the matrices,

each element in the cube can be one zero or negative one.

The matrix product C is created by combining elements from matrices A and B, like this.

And so on.

Until you have the full matrix multiplication tensor.

Now, you can use a process called tensor decomposition to

break down this 3D tensor into building blocks.

Similar to taking apart a cube puzzle.

One natural way to break tensors down is into what's called rank-1 tensors,

which are just products of vectors.

The trick is each rank-1 tensor here describes a multiplication step

in a matrix multiplication algorithm.

For example, this rank-1 tensor represents the

first multiplication step in the standard algorithm: A1 times B1.

The next rank-1 tensor represents A2 times B3.

Adding these two rank one tensors yields the first element in the product C1.

Here are the next two rank-1 tensors, representing the

multiplications, A1 times B2 and A2 times B4, which form C2.

Eventually, the entire standard algorithm with its eight

multiplication steps is represented by decomposing the

3D tensor into eight rank-1 tensors.

These all add back up into the original 3D tensor.

But it's possible to decompose a 3D tensor in different ways.

Strassen's seven multiplication steps for the same two by two

matrix multiplication looks like this.

These rank-1 tensors are more complex.

And this is still a full decomposition, but in fewer steps,

which add backup to the original tensor.

So the fewer rank-1 tensors, you use to fully decompose a 3D tensor,

the fewer multiplication steps used in the tensor's corresponding matrix multiplication.

DeepMind's construction of a single-player game

for AlphaTensor to play, and learn from was key.

Find an algorithm for this matrix multiplication that requires the fewest

multiplication steps possible... is a vague request.

But it becomes a clearly defined computer task

once it's formulated as: decompose this 3D tensor

using as few unique rank-1 tensors as possible,

It's really hard to describe what, what the search space looks like.

In the particular case of matrix multiplication,

that's, that's quite, it's quite convenient to formulate it in that space,

because then we can deploy our search techniques

and our machine learning techniques in order to search in that very,

very large, but formalizable search spaces.

AlphaTensor's play was simple.

It was programmed to guess rank-1 tensors to subtract from the original 3D tensor,

to decompose it down to zero.

The fewer rank one tensors it used,

the more rewards that got.

Each rank-1 tensor that you remove from from the 3D tensor,

is has a cost, has a cost of let's say one.

And so we want to figure out what's the way of achieving the goal with the fewest penalties.

And so that's what the system is trying to learn how to do

it's learning to estimate, well when I'm in this kind of configuration,

roughly how many penalties do I think I'm going to incur

before I get to the goal?

But tensor decomposition is not an easy game to master.

For even a three by three matrix multiplication

with only elements zero or one,

the number of possible tensor decompositions

exceeds the number of atoms in the universe.

Still, over the course of its training,

AlphaTensor started to home in on patterns to decompose the tensor efficiently.

Within minutes it rediscovered Strassen's algorithm.

Then the program went even further.

It beat Strassen's algorithm for multiplying two, four by four matrices

in modulo-2, where the elements are only zero or one,

breaking the 50 year record.

Instead of the standard algorithms 64 multiplication steps

or Strassen's 49,

AlphaTensor's algorithm used only 47 multiplications.

AlphaTensor also discovered thousands of other new fast algorithms,

including ones for five by five matrices in modulo-2 .

So, will programs like AlphaTensor,

churning away in server rooms

pulling out new mathematical discoveries from lines of code

make mathematicians obsolete?

Ultimately, I think this will not replace like the

mathematicians or, or anything like that.

This I think provides a good tool that can help mathematicians find new results

and guide their intuition.

That's exactly what happened just days after the AlphaTensor results

were first published in the journal Nature.

Two mathematicians in Austria, Manuel, Kauers and Jakob Moosbauer

used AlphaTensors 96-step, five by five matrix multiplication algorithm

as inspiration to push even further.

And then Jakob suggested we just take the algorithm

that the AlphaTensor people found

as a starting point and see whether

there's something in the neighborhood of this, and we

could have an additional drop.

And indeed, that that was the case.

So it was a very short computation for,

for our new mechanism that was able to reduce the 96 to 95.

And this we then published in the arxiv paper.

The right way to look at this is, as a fantastic example of a

collaboration between a particular kind of technology

and mathematicians.

The true potential for human and artificial intelligence collaboration

is a frontier that is only now being fully explored.

I don't think people can be made

irrelevant by any of this kind of work

I think it empowers people to do more.