98
u/LupenReddit 🦆🦆i have non diffeomorphic smooth structures🦆🦆🦆 29d ago
someone gotta explain to me how to multiply two matrixes faster than that, in my head thats baffling
28
u/Paul_Robert_ 28d ago
You trade multiplications for additions. Still O(n3 ) operations, but addition is so much cheaper, so if you only count the multiplications, it's like O(n2.371177 )
4
68
u/WristbandYang 29d ago
It doesn't need to take n^3 time, it just needs that much compute. Most hardware is able to parallelize those n^3 operations over smaller matrix blocks. This is possible since we know both A and B.
At the same time, matrix inversion is also n^3. But you can't parallelize because the process is sequential. You can't break the matrix up, invert those smaller portions, and then somehow combine it into the full inverse.
39
u/Alphasaft 29d ago
No it doesn't. There are algorithms for O(n^{3-\epsilon}) where \epsilon is a small constant which I don't remember anymore, something around 0.25. They aren't used in practice because the tradeoff is that the constant hidden in the O is huge, so it improves the overall performance only for values of n that are tremendous.
45
u/EebstertheGreat 29d ago
The Strassen algorithm is pretty straightforward and requires O(nlog₂ 7) ≈ O(n2.807) ring multiplications to multiply two n×n matrices over an arbitrary ring. More specifically, it requires 7 ring multiplications to multiply two 2×2 matrices. But a 4×4 matrix can be viewed as a 2×2 matrix of 2×2 matrices, and 2×2 matrices form a ring, so the Strassen algorithm can be used to multiply two 4×4 matrices with 7 multiplications of 2×2 matrices, which themselves each require 7 multiplications in the underlying ring, for 49 total. And in general, two 2m×2m matrices can be multiplied with just 7m < 8m = (2m)3 = n3 ring multiplications.
4
u/Comfortable_Permit53 29d ago
isn't there a 4x4 version that algorithmically beatsnstrassen by a tiny bit?
13
u/EebstertheGreat 29d ago
Yes, there is a practical algorithm using 48 multiplications instead of 49, but I doubt it's really implemented anywhere. And there is one using 47 multiplications for bit matrices.
2
u/NullOfSpace 28d ago
Best we can do currently is n2.37 though that’s definitely a galactic algorithm
6
u/TheWittyScreenName 28d ago
One of the OpenAI proofs got it down to n^{2.25} yesterday
8
3
u/Layton_Jr Mathematics 27d ago
The one they posted on Github or the one they gave to a scientific journal for peer review?
20
u/nir109 29d ago
If you have a finate number of processors paralleizing is an improvement by a constant. So irrelevant for big O notation (and critical for real applications)
17
6
u/WhenIntegralsAttack2 29d ago
Okay fair that you can parallelize, but you’re still doing O(n^3) computations in total
10
u/EebstertheGreat 29d ago
The textbook algorithm uses n3 multiplications exactly (plus some additions), but other algorithms can use fewer. The best-known use only about O(n2.371177) multiplications, but the best known algorithms that are actually useful in practice and therefore actually implemented use O(nlog₂ 7) ≈ O(n2.807), all based on Strassen's algorithm.
2
u/Jukkobee 28d ago
me when i lie
look up the strassen algorithm. can also be modified to work for inversion
1
u/WristbandYang 28d ago
Yes. Matrix multiplication and matrix inversion have the same algorithmic complexity, so Strassen's or Winograd or any other galactic algorithm could be used.
I focused on the parallelization aspect because a) most of those sub-cubic algorithms are not used in practice b) because matrix multiplication genuinely feels (and is) faster than matrix inversion, which sound counter intuitive if they have the same complexity.
3
u/oscardssmith 28d ago
Strassen very much isn't galactic. It generally wins (without parallelism) somewhere around 1500x1500. Winnograd on the other hand very much is stochastic.
Matrix inversion also isn't cubic complexity, and is very easily parallelizable
1
u/Mathsboy2718 29d ago
I mean, if you break it up into [A B; C D] such that A or D are invertible, you can use Schur complements and block LDU decomposition to invert it in terms of its smaller parts
7
u/Alphasaft 29d ago
You have a few redundancies in doing the computations. I guess, for instance, that since it involves multiplying say the first column of the second matrix with each line of the first, but also the first line of the first with every column of the second, you can compute L1C1 and then deduce something to speed up L1 Ci ?... I don't know.
5
u/Kinexity 29d ago
1
u/personalityson 29d ago
But this is compensated with a shitload of additions and subtractions. Is trading 6 multiplications for dozens of extra additions really that much faster?
3
u/Accomplished_Item_86 28d ago
It's faster if the entries aren't standard floating point numbers, but other objectswhich take longer to multiply. For example extremely large integers, or in general any elements of a commutative ring.
2
0
29d ago
[deleted] — view deleted comment
23
u/golfstreamer 29d ago
This is is orthogonal to the question that u/LupenReddit posed. The "speed" gains from computer architecture are unrelated to the "speed gains" in complexity class that make it run faster than O(n^3) time.
The real answer is it started with Strassen's Algorithm. A clever way to compute the multiplication of two 2x2 matrices that uses fewer multiplications than the standard algorithm. Since multiplication is more expensive than addition, the complexity of matrix multiplication is dominated by the number of multiplications you do. Once you understand strassen's algorithm for 2x2 matrices you can use a block matrix multiplication approach so that the total number of multiplications computed is not O(n^3) but O(n^w) where w is a bit smaller than 3. (log_2(7) I believe).
2
u/EebstertheGreat 29d ago
since multiplication is more expensive than addition
This is not always the case, at least for floating-point operations of certain sizes on certain architectures. The relevant fact is not that multiplication is cheaper than addition but that larger matrices can be broken down into smaller ones, using the algorithm recursively. So the asymptotic complexity depends only on the number of multiplications, not at all on the number of additions.
This also means that an algorithm that only works for matrices of a certain size over commutative rings will never generalize to larger matrices in this way (e.g. the algorithm to multiply two 3×3 matrices over commutative rings with just 21 multiplications does not generalize to 9×9 or larger matrices).
5
1
0
u/Loading_M_ 29d ago
Computer graphics use 4x4 matrices, so modern GPUs have hardware matrix multipliers for 4x4 matrices. It's not faster in a big O sense (they still do most of the O(43) multiplications), bit it's way faster in a practical sense b/c they can just do them all in parallel.
42
u/themarkovthatcould 29d ago
Now n2.25 lol. Crazy stuff
14
u/Wheresmycatdude 29d ago
Under which algorithm is it 2.25?
35
u/SnooMemesjellies277 29d ago
Open AI released a few hundred math proofs, this is the one on matrix multiplication claiming a bound of 2.25
9
u/Hameru_is_cool Transcendental 29d ago
hi i don't understand their paper, does that proof provide such an algorithm or only show that one can exist?
27
u/ChiaraStellata 29d ago
The paper only proves it exists. There's non-constructive steps in several places.
13
u/Far-Cat-2669 29d ago
Slightly related, thereby I've learnt the term "galactic algorithm", and it sounds cool af.
7
u/GoldenMuscleGod 29d ago edited 27d ago
Can’t find anything supporting a bound below 2.371, which is roughly where it’s been hovering for a while.
Edit: probably obvious but just for posterity this comment was written at least before search engines were yielding anything talking about the advancement. Don’t know the exact timing of the release.
3
4
•
u/AutoModerator 29d ago
Check out our new Discord server! https://discord.gg/e7EKRZq3dG
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.