The fastest matrix multiplication algorithm

0:00 Multiplying Matrices the standard way
2:05 The Strassen Method for 2x2 Matrices
3:52 Large matrices via induction
7:25 The history and the future

In this video we explore how to multiply very large matrices as computationally efficiently as possible. Then standard algorithm from linear algebra results in n^3 multiplications to multiply nxn matrices. But can we do better? The Strassen algorithm improved this to about n^2.8, first in the 2x2 case and then we can prove via induction it works in general. This improvement has seen a range of improvements over the last 50 years inching closer - but still far away - to the theoretically limit of n^2.

Further Reading:

Check out my MATH MERCH line in collaboration with Beautiful Equations

COURSE PLAYLISTS:

OTHER PLAYLISTS:
► Learning Math Series
►Cool Math Series:

BECOME A MEMBER:

MATH BOOKS I LOVE (affilliate link):

SOCIALS:

[planaritytheory]

It's important to note that, although additions _are_ considered cheaper than multiplications, what we _aren't_ doing is making a tradeoff between the two operations (accepting many more additions to save a few multiplications). You didn't explicitly say that's what's going on, but someone could get the impression from this video that that's the deal---I myself used to think that. Instead, the number of additions, multiplications, and total number of operations are all lower for Strassen's algorithm, and it's because the number of "multiplications" at each step is counting the number of recursive calls that are made.

[Mattes_H]

I think it should be noted that all of these faster algorithms are so called galactic algorithms, meaning the constant that is hidden by the phrase "order of" is so big they become useless for any practical application.
In practice the challange is more about efficent and parallel implemetation. In fact GEMM the subroutine most often used for matrix-matrix-multiplication usally implements either the naive or Strassen-based algorithm but uses all the hardware tricks available on modern processors to get their high perforamce.

[cbunix]

I wrote a cache friendly matrix multiplication algorithm that improves performance by 40% when matrices are very large; basically, the multiplications and additions are the same, but the order is done in a way that respects cache memory.

[michaelsaba]

Just read about this algorithm in CLRS. It's a perfect teaching tool to show why constant factors might not matter in asymptotic notations, but how they often do matter when working with recurrences. Like in this case, where 7 multiplications are preffered over 8, even if we're only multiplying the runtime by a constant factor. Strassen's yields a Theta(n^log(7)) time complexity, while the standard divide and conquer approach yields Theta(n^3) time.

[frfr]

It reminds me of this algorithm for natural numbers multiplication, which is theoretically a lot faster than any other algorithm we know of, but gets worth using only at ridiculously huge numbers. I can't remember how its called, but i think it was mentioned in 3b1b's latest video on convolutions

[magicflour]

I had a class where a whole third of it was dedicated to these linear algebra algorithms. The most I learned really was "optimize the hardware and optimize with hardware" to get good results lol. This was a computer engineering class so it made sense.

[alphalunamare]

Fascinating! It brings back old memories. In 1977 I was mulling over the problem and managed, over a few days, to create an algorithm for 3x3 multiplications requiring 24 multiplications and 66 additions only. It reduced to strassen's method in the 2x2 case but was no improvement as that would have required 21 multiplications. I did this longhand over yards of line printer paper. Unfortunately a Canadian published an algorithm with 23 multiplications and 96 additions. it pissed me off no end, especially as it had no information regarding its derivation. (If I could trade 1 multiplication for 29 additions I could improve but I left it on the shelf) Sulking I guess. Over the years I wondered if it was just a novelty, then I realised that in an object oriented sense that the savings are manifestly more than for just simple arithmetic multiplications. An intriguing thought is whether the intermediate Pn multiplications of 'objects' have a real meaning in the physics of the model under analysis that perhaps could shed some light? Perhaps in the Geometric Algebraic treatment of Spacetime?

[eti-iniER]

As a first year CS student, I'm completely blown away by the fact that humans know and understand concepts like this. Amazing video, btw

Cue the mild depression

[kruksog]

I remember learning the Karatsuba algorithm for multiplication. It is also computationally cheaper than the standard way of multiplying numbers. It had a very similar feel to this.

Cool stuff. Thanks!

[wcdeich]

Interesting! I previously knew some algorithms could do matrix multiplication faster for large sparse matrices, but those algorithms are actually slower for large dense matrices.

[discreet_boson]

Please make more computational math videos like this!
Programming documentation never explains the math like you do

[LZY]

There is a thing calleg "Hierarchical matrix", that allows to change a matrix to a more "compact" form that allows to compute many operations like inversion or multiplication in almost O(n) time. If I remember correctly if we remove the constant (k) that controls approximation the complexity is about O(n * (logn) ^ 2)

[adamel-sawaf]

Great vid! Just as informative as it needed to be, while sparking inspiration to learn more. One thing I think you should’ve mentioned was how much the space complexity grows for the trade-off in speed.

[prashantsingh]

As someone who absolutely loved solving matrices & determinants problems in higher secondary mathematics, way back in 2011-12, a huge thumbs up for the excellent video. 👍

[airsquid]

The amount of power I wield is unrivaled with this knowledge, thank you for yet another interesting video full of passion!!

[quarkonium]

One thing to keep in mind is that most of these improvements from the Strassen algorithm are theoretical. Most only improve on the Strassen algorithm for extremely large matrices-so large that these algorithms will probably never be practical

[mohammadhomsee]

That's a great videos, I really love to hear your lessons. Good job professor!

[cmilkau]

One important question with this algorithm: how many additions does the recursive algorithm use? Because in the end, we want a faster algorithm, not just a reduction in elementary multiplications. It's also a bit counterintuitive that this strategy *reduces* the total number of additions asymptotically.

[ddognine]

Interesting video of an area of active research of which I was unaware. I would be interested in a similar video covering the state of the art in matrix inversion which I believe is much more problematic for large matrices than multiplication and is typically the first operation before any multiplication.

[guigazalu]

While watching, I asked myself if you would cite the AlphaTensor article and results, as I read it in the recent months.
It turned out you did! It is a very cool article, even though it's a "heavy reading" for me.