Searching for the world's fastest way to multiply two matrices

Science · Published 29 October 2026 Swipe more like this →

In short: Standard linear algebra teaches us that multiplying two nxn matrices requires n^3 operations. But mathematicians have spent decades trying to break this barrier, searching for a theoretical limit of n^2. While humans have made progress, the most efficient method for even small matrices remains a mystery.

The standard algorithm for matrix multiplication scales at a complexity of n^3 multiplications for nxn matrices. This means doubling the size of your data increases the computational work by a factor of eight. To overcome this, researchers look for algorithms that reduce the exponent in the complexity formula.

Strassen's algorithm was a landmark breakthrough, improving the complexity to approximately n^2.8. While it works for 2x2 matrices and can be generalized via induction, it is still far from the theoretical goal of n^2. Over the last 50 years, various refinements have slowly pushed this number down, but the gap remains significant.

The problem can be reframed as finding low-rank decompositions of a specific three-dimensional (3D) tensor called the matrix multiplication tensor. While we have had efficient polynomial-time algorithms for two-dimensional matrices for over 200 years, finding these decompositions for 3D tensors is an NP-hard problem. The search space is so vast that even the optimal algorithm for multiplying just two 3x3 matrices has not been discovered.

To tackle this, researchers are moving beyond human-designed heuristics—which are likely suboptimal—toward artificial intelligence. A new approach uses deep reinforcement learning (DRL) to navigate a game called TensorGame. In this environment, an agent named AlphaTensor must choose how to combine matrix entries from an action space of over 10^12 possibilities. By using DRL to recognize patterns in tensors, the goal is to discover provably correct and practical algorithms that humans might never conceive.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

• How matrices multiply and the power of their factorizations
• A matrix is a rectangle that eats vectors and spits maps
• How computers break down complex matrices to solve systems of linear equations efficiently
• Divide and conquer is the secret to solving the world's most complex computational problems.
• The secret math that powers your digital world's biggest secrets
• The complex fluid dynamics hidden in a bug's bathroom break
• How 1,024 slow processors can outperform the world's fastest single engine
• The vast regions of our planet we have simply stopped exploring
• Why is the universe silent, and what does it mean for our future?
• Reality is not found; it is built in real time
• Was the Tyrannosaurus Rex actually different than we once imagined?
• Why your brain sees a different dress than your neighbor

More in Science · Latest · A–Z · All topics