Matrix multiplication inches closer to mythic goal
quantamagazine.org
quantamagazine.org
On all modern CPUs their speed is the same for float numbers. Specifically, they have 4 cycles of latency on Skylake, 3 cycles of latency on Zen2, throughput (for 32-byte vectors) is 0.5 cycles for both CPUs.
If you look at Strassens algorithm [1] you see that it splits each matrix in 4 blocks. Naively you can do 8 multiplications of those blocks, as well as 4 matrix additions, and recover the full matrix multiplication.
If T(n) is the number of operations (additions as well as multiplications) for an nxn matrix multiplication, we can write the equation T(n) = 8T(n/2) + 4(n/2)^2. If we solve this, we end up with T(n) ~ n^3, which is of course the time complexity of naive matrix multiplication.
However, with Strassen you end up with 7 smaller matrix multiplications and 18 matrix additions. The equation we get now is T(n) = 7T(n/2) + 18(n/2)^2. We end up with T(n) ~ n^(2.8).
We see that when we save _matrix_ multiplications we eventually end up saving both elementary multiplications _and_ additions.
That probably isn't directly the point either. Perhaps new methods could lead to practical performance improvements in the long run, but my impression is that the recent improvements have been more of theoretical than practical interest.
Even the asymptotic improvements are getting rather minuscule, though.
Edit: shoulda read to the end, it says that Strassen says no.
I know that I have a lot of math background, and my brain read that log(n) as part of the exponent. I figure that if I read it that way, you have to expect that others will as well.
Also, putting a constant factor like log(2) inside big-O notation is meaningless.
Unfortunately this was just word of mouth, and I might be misremembering.
> Don Knuth: As you say, I've come to believe that P = N P, namely that there does exist an integer M and an algorithm that will solve every n-bit problem belonging to the class N P in nM elementary steps.
> Some of my reasoning is admittedly naïve: It's hard to believe that P ≠ N P and that so many brilliant people have failed to discover why. On the other hand if you imagine a number M that's finite but incredibly large—like say the number 10 3 discussed in my paper on "coping with finiteness"—then there's a humongous number of possible algorithms that do nM bitwise or addition or shift operations on n given bits, and it's really hard to believe that all of those algorithms fail.
> My main point, however, is that I don't believe that the equality P = N P will turn out to be helpful even if it is proved, because such a proof will almost surely be nonconstructive. Although I think M probably exists, I also think human beings will never know such a value. I even suspect that nobody will even know an upper bound on M.
O(n^2 * ln(n)).
Waxing theoretically, there is some integer-valued function f such that optimal matrix multiplication is
Ω(n^2 * f(n)).
We can ask whether f is O(1). I think your statement is equivalent to saying that f is o(n^ε) for any ε > 0.
Yes you're right it would be true. We can see this by just constructing a sequence of algorithms A_i that are implementations of the putative optimal O(n^2 * ln(n)) algorithm except artificially slowed down by ever smaller polynomial overheads. But the hypothesis I'm describing above holds that no such O(n^2 * ln(n)) algorithm exists.
> Waxing theoretically, there is some integer-valued function f such that optimal matrix multiplication is...
The hypothesis I'm describing is that no optimal algorithm exists. Instead, the claim is that there is an infinite sequence of ever better algorithms (specified by ever longer sets of instructions, and with ever larger constant overheads).
[1] http://www.thi.informatik.uni-frankfurt.de/~jukna/Strassen-V...
Now you want to see how fast it can really go if you are prepared to spend (say) $100k on the hardware (e.g. 64 times as many CPUs with some fancy interconnect fabric). How about spending $100M? It turns out that moving all this data around is also quite costly.....
Saying time complexity has nothing to do with hardware is like saying speed limits have nothing to do with cars. Hardware constraints are the entire reason we developed the notion of time complexity.
I'm honestly very confused as to how someone (I assume is) engaged in programming could think the relationship is tangential.
Now that we are on the same page, of course the asymptotic complexity of a method matters, but some of the lowest complexity methods actually have huge constants and cannot be used until you get to scales that dwarf most usages. This means that the connection is tangential. The current method of matrix multiply used in all your software is NOT the lowest asymptotic complexity method. Look it up.
For perspective, that would be akin to multiplying every MAC address with every other MAC address upon the entire IPv4 range.
I don't know how to use O() notation for GPUs but it should be something like O(n^2/k^2) where K is the tile size [0].
Also lower memory bandwidth becomes a bottleneck here. So there is a lot of optimizations done on how to transfer from CPU to GPU and then within GPU to efficiently query the matrices.
[0]https://docs.nvidia.com/deeplearning/performance/dl-performa...
It brings us closer more than anything I've done, that's for sure.
I agree with your sense of taste about which problems are personally interesting, and likely to be significant in my lifetime. But I still think it's cool that there are theoretical developments like this. Refining bounds is a cool way to see theoretical progress quantitatively.
I think also it's more like discovering what pi is than trying to find the next digit. We know a lot more about pi than we do about the lowest achievable exponent.
One of the major failure modes of academia is that students are generally not very good at picking problems, and can end up following their advisors down a blind alley. The underlying question here is absolutely worthwhile, but spending a year extending laser will have no impact. It's like you're trying to dig to the center of the earth and someone hands you a shovel: do you take it and start digging, or walk away and try to find/invent an oil drill?
complexity is wrt a particular model of computation - a turing machine. turing machines are sequential (NTMs aren't). run time on a parallel model is not necessarily a constant off from run time on a sequential model.
http://www.ijcee.org/vol9/949-E1621.pdf
you edited your comment. it said what's the speed up on GPUs (which i provided).
>GPUs are not nondeterministic Turing machines
for small problem size that's exactly what they are (or any multicore cpu for that matter)
>The other is to imagine that the machine "branches" into many copies, each of which follows one of the possible transitions. Whereas a DTM has a single "computation path" that it follows, an NTM has a "computation tree".
https://en.wikipedia.org/wiki/Nondeterministic_Turing_machin...
O notation does not apply to small problems. It is strictly concerned with asymptotic behavior.
It's true that for small problems they are indistinguishable, but in the context of discussing big O notation that is irrelevant.
For the purposes of computing asymptotic time complexity, whether the algorithm is run on a 1 core system or an M core system is usually irrelevant.
That's not how you do big-O with parallel systems.
When talking a parallel algorithm, you often perform two different big-O calculations:
* Breadth: "If a single-processor" executed the parallel algorithm, how long would it take? (If the best sequential algorithm and best parallel algorithm are both within a constant-factor of breadth, its called "work-efficient"). Also called "Total Work"
* Depth: "If an infinite number of processors" executed the parallel algorithm, how long would it take? Also called "Length of the longest dependency chain".
A naive matrix-multiplication would be O(n^3) breadth. I don't know the depth calculation unfortunately...
---------
For example, Bitonic Sort is one of the best GPU-sorting algorithms, but its O(n * log^2(n)) Breadth... asymptotically slower than sequential's O(n*log(n)) time.
But Bitonic Sort is often used because its Depth is O(log^2(n)). Which means that "with enough processors", you approach O(log^2(n)) sorting time, which is pretty amazing.
Note: "GPU Mergepath" is pretty damn amazing if you've never seen it before. O(n) breadth to perform a merge operation (part of merge-sort), so for large arrays, Mergesort wins as long as you use the GPU Mergepath algorithm to perform the individual merge steps.
But if you have more processors than data (lol, it happens: Vega64 supports 163,840 threads of execution: Occupancy 10 x 4096 physical cores x innate hardware parallelism over 4 clock ticks), Bitonic sort is an obvious choice.
If I have at least n^2 processors, I can send a row and column to each processor, which can compute the inner product in linear time. So O(n^2) time to coordinate the work, and O(n) to actually do it.
-----------
Processors are generally assumed to be self-numbered. Ex: processor #100 knows its processor#100.
xloc = (threadIdx.x % matrix_width);
yloc = (threadIdx.x / matrix_width);
performMatrixCalc(xloc,yloc);
As another poster commented, these are O(N^3) in work, not necessarily the wall clock time you see due to parallel speedup and cache effects, but will scale as O(N^3) once you're at a size past all of these. These implementations are highly tuned and optimized for hardware, much much more so than the naive 3 loop implementation. The predictable and 'easy' access patterns make the simple algorithm hard to beat.
To understand why this even happens, let's say we want to compute the expression A*B + B*A for matrices A and B. One way we can do this is to compute the products A*B and B*A naively: two multiplications are needed. A trickier way to do this is to introduce a parameter x: we will instead compute A*A and (x*A + B/x)*(x*A + B/x) = x^2 A*A + (A*B + B*A) + x^-2 B*B. Thus (x*A + B/x)*(x*A + B/x) - x^2 A*A = (A*B + B*A) + x^-2 B*B: if x is large enough the second term vanishes and we can employ the rounding trick from before. Now this still needed two multiplications, but here one of our multiplications was A*A. If later we needed to compute A*C + C*A in the algorithm, we could then do that in only 1 additional matrix multiplication by repeating the trick. A more sophisticated version of this algorithm underlies all known approaches for matrix multiplication beyond w << 2.8.
[0] https://nla-group.org/2020/07/21/numerical-behaviour-of-tens...
Maybe my linear algebra is REALLY rusty, but I that doesn't seem right to me.
For two 4x4 matrices, each element in the output matrix will be the sum of four products. So each of the 16 output elements will require 3 additions, and you'll need a total of 48 additions.
I'm not sure where they're getting "16 additions" from.
To multiply two nxn matrices according to the textbook method, I think you'll need n^3 multiplications and n^3-n^2 additions.
I don't doubt that the multiplication time dominates the algorithm. Maybe this is just a nitpick.
As matrices grow larger, the number of multiplications needed to find their product increases much faster than the number of additions.
The whole paragraph is talking about the multiplications and additions needed to find the product of two matrices.
Can anyone clarify what "as physically possible" means here? Are there physical systems that perform matrix multiplication in O(n^2) ? (I feel silly even asking that about a physical, non-computation system)
I remember there were applications of optical computation, including a startup that wanted to accelerate deep network inference through optical computation: they had a way to do matrix multiplication using a projector (for the data matrix) and a 3D printed lens (for the network weights).
You need n^2 time just to read the two matrices, so I always thought of that as a natural lower bound. (Of course, we're talking about multiplications eventually here, so may not be exactly what they meant...)
A square matrix with n rows and columns has n^2 entries, so if you need to look at all the entries in two matrices to compute their product, then you need to do O(n^2) work just to look at all the relevant entries.
The only way you could get around this is if you know many entries are 0, or identical, or have some other structure such that you don’t need to look at them separately.
Every matrix multiplication can be boiled down to multiplying rows by columns. This is definitionally required for matrix multiplication, so that is the lower bound for how many multiplications are required. One multiplication for every final element in the n x n matrix, or n^2.
To answer the GP, the minimum amount of work necessary is to write a number for each element in the array, which scales by n^2 since there are n^2 elements. It is of course only possible to beat this if you can make assumptions like “the diagonal of my matrix is nonzero and everything else is zero”, but that’s not general matrix multiplication anymore, that’s a specialized sparse matrix routine. For a dense, “normal” matrix, O(n^2) is the absolute best we could hope for.
Reads from the original two matrices and writes to the final matrix aren't at all the crux of the problem, so I don't think it makes sense to focus on either of those things in your explanation. The goal of the problem is to reduce the number of multiplications which are required to find the values that you then write (of which there will always be n^2 writes). There will also be 2n^2 reads, but likewise that isn't relevant because it's not what you're trying to optimize.
The relevant idea here is that the naive method of multiplying a matrix involves n multiplications for every row-column pair, for a total time complexity of n^3 (n rows, n cols, n multiplications). The goal here is to bring down that third number, from n down to something >= 1, with the holy grail obviously being 1 itself.
It's not at all obvious to me why the number of multiplications must be at least n². Can you prove that? (To be clear, n² multiplications is most certainly the lower bound, but I can't come up with a good argument as to why.)
This is why the trivial "you must read n² entries from each input matrix and write n² entries in the end" is helpful: It's an extremely obvious lower bound on the asymptotic complexity. Sure, it's not what we're trying to reduce (and getting < n² multiplications would be a ridiculous result), but anyone can see that it's true.
> you (by definition) need to multiply them by each other at least once
Why does multiplying a row with a column require at least one multiplication? "By definition" it takes n multiplications (!), but in the context of matrix multiplication we can do it with less - possibly with O(1) multiplications. And it seems neither you nor me can come up with a good argument why it can't take less, despite discussing it for a while.
Which is why "you need to write n² entries" is used as an argument for the O(n²) bound, even if it has nothing to do with the number of multiplications.
To be honest I’m not sure whether that really proves it. Does computing a single multiplication require a multiplication?
A couch expert on computer architecture here, but a large enough systolic array could be used to achieve their "physically possible" limit? [0]
New CUDA GPUs have been coming with these tensor cores that are just systolic arrays. Google's TPU are the same.
Could someone with more knowledge on systolic arrays comment on whether a large systolic array can achieve this?
[0] https://medium.com/intuitionmachine/googles-ai-processor-is-...
You cannot reduce the number of operations by waving a magic architecture want. Hence the no. But you can do operations in parallel rather than in series. Same number of operations, but it takes less time.
So if a systolic array is built for the same scale as your problem, your bottleneck does indeed become how quickly you can send data to/from that dedicated system.
You _do_ actually have to read all the entries in both matrices -- if you know K-1 out of K values then in general you still can't uniquely compute the output of matrix multiplication. Consequently, any algorithm relying on only some subset of the entries is at best an approximation.
If you have more information (e.g., that one or both of the matrices is sufficiently sparse) then you can potentially do better.
https://www.cs.utexas.edu/users/flame/pubs/FLAWN79.pdf
You're right though afaik all the other algorithms are still 'galactic' and completely impractical
Fifty years ago multiplication was vastly slower than RAM access. Nowadays it's pratically free compared to even getting data out of cache ...
https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a...
Edit: ah, we're probably talking about the same thing. Strassen was 1970.
[0] https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
An optimal arrangement for n==4 already exists. Both AMD MI100 and NVidia Volta / Ampere perform 4x4 FP16 matrix multiplication in a single assembly language statement.
An 8x8 matrix is just an arrangement of four 4x4 matricies (!!!!). As such, you can define a 8x8 matrix multiplication as a 4x4 matrix multiplication over 4x4 matricies. This recursive relationship is often key to how they manage to get faster-and-faster. Getting to O(n^2.8), or O(n^2.6,) etc. etc.
I’ve now got the crazy desire to see matrices and vectors built into every language in a clean and succinct way.
For example:
10 DIM A(3,3),B(3,3),C(3,3)
20 MAT READ A
30 DATA 1,-5,7, .45,23,9, -5,-1,0
40 MAT B=A:REM assignment
50 MAT B=ZER:REM zero array
60 MAT B=CON:REM all 1s
70 MAT B=IDN:REM identity
80 MAT B=TRN(A):REM transpose
90 MAT B=(2)*A:REM scale
100 MAT B=INV(A),D:REM invert array, determinant in scalar D
110 MAT C=A*B:REM matrix multiplication
120 MAT PRINT C:REM prints something close to an IDN arrayHis only computer was a Commodore 64 and he had written all the software himself in BASIC over the years, just translating a lifetime of professional experience into these little interactive programs on floppies.
Maybe the modern equivalent would be to use Excel.
The GE-635 (https://en.wikipedia.org/wiki/GE-600_series) that it ran on most of its life could have 4 CPUs, had protected memory and floating point hardware, and supported at least 200 kilowords of memory (http://www.bitsavers.org/pdf/ge/GE-6xx/CPB-371A_GE-635_Syste...)
At 36 bits/word, that’s 900 kilobytes.
The first version of Microsoft basic (https://en.wikipedia.org/wiki/Altair_BASIC) ran in 4 kilobytes (leaving about ¾ kilobytes for programs and data), so it’s understandable that it lacked some features (it didn’t even have else clauses in if statements, had SIN, but not COS or TAN, didn’t support integer or string variables, etc))
It’s not as if they don’t know matrices exist. Excel has matrix operations (https://support.microsoft.com/en-us/office/mmult-function-40...)
not rhetorical, genuine question.
That said, I would love to have good data science library support (bindings to stuff like BLAS/LAPACK, Torch, Stan, etc) in Idris.
Imagine vector and matrix dimensions checked at compile time. Probabilities guaranteed to be between 0 and 1, checked at compile time. Compile-time enforcement that you are handling "nil/null" data inputs correctly when reading data from a database or CSV file. Writing a web scraper with linear types to help catch bugs & performance leaks. Maybe even proving theorems about the math code you're writing ("is this a valid way to express X"?).
Maybe not ideal for rapid exploratory model development, but it'd be pretty damn cool for writing data science tooling/libraries and "production" ML code in my opinion.
https://github.com/deepmind/tensor_annotations seems promising. I've developed a mypy plugin for pytorch that does similarly off of the "Named Tensor" dynamic feature (which isn't well supported yet), but haven't released it yet.
I'm also excited by the ways in which including this in some sort of "first-class" way could make tensor semantics simpler, which I'm assuming xarray allows? Many of the operations enabled by http://nlp.seas.harvard.edu/NamedTensor are quite nice and similar ideas can let you write more generic code (ie. code that works automatically for on tensors with and without a batch dimension)
Once you get your head around everything being a vector, R can be a lot of fun.
I love Julia but I wish I didnt need to explicitly broadcast functions across a vector.
5 * A
5 + A
5 .+ A
The Julia approach also has some drawbacks, I was writing some code the other day and forgot to broadcast exp() across a matrix. exp(A) and exp.(A) gives very different results but it's not immediately obvious looking at code, especially when the code is a mixture of broadcasted and native matrix function calls which dots peppered all over the place.
I understand it's an easy mistake to make when you're used to R or Numpy, but I'd say it's their fault you're making this mistake, not Julia's.
I was pointing out one downside of the broadcast syntax, is that a typo can lead to non-obvious errors in calculations. R avoids this with a expm() function.
Don't get me wrong, I love using Julia, it makes turning maths into code easy, and this is not even close to a deal breaker.
E.g. I could just as easily write
"one downside of autovectorization, is that a typo can lead to non-obvious errors in calculations. When I want the exponential of a matrix, I might accidentally write exp(M) and get unwanted vectorization. This is a typo that can lead to non-obvious errors in calculations. Julia avoids this with a exp.(M) syntax."
I think the potential for typos is symmetric here between julia and R. I think what's asymmetric though is that Julia's broadcasting is more extensible, less and hoc and more general than R's auto-vectorization since it can be done over arbitrary containers and you can control precisely what calls broadcast.
______________________________
Sorry if this comes off as confrontational, that's not my intention. I just think this is a very interesting and fruitful corner of language design.
Confirmed Strassen thinks the lower bound is n^2.32192809489.
Second of all, algorithms aren't patentable. The only way to keep it exclusive would be to keep it secret. I can't think of any examples of a private company making a major scientific or mathematical breakthrough and then keeping it secret long enough to profit off of it.
I wish. The RSA cryptosystem was patented and under license until 2000 in the US, even though the math wasn't secret.
Algorithms absolutely are patentable because they are computing "machines." It's mathematical equations that aren't patentable, because they're closer to laws of nature.
It's not really designed to be optimal for the current hardware, but just to lower the number of steps. It could be more useful in the future though.
It most certainly won't [0]. But neither will something like 99% of mathematical research right now.
[0]: See first example in https://en.wikipedia.org/wiki/Galactic_algorithm
I pitched them a paper magazine a few years ago, because I wish I could leave these around for my kids to flip through, but no joy yet..
Those summaries will be written in a similarly ephemeral format. A book in a library can sit there and be rediscovered in a hundred years. A scroll or an engraving in a thousand. But we create things that have evaporated in a mere decade.
Even thought of etching that on stainless plates or something.
Could be scanned with a smartphone or even decoded by hand (include an ASCII lookup table).
I have a wedding photograph printed on non-biodegradable material (not intentionally for preservation, it's decorative), and perhaps that will eventually be the only tangible evidence of me in the same way that wedding photographs are all I've seen of some relatives born before 1900.
I'd wager we're 20 - 30 years out from regenerative cloning, and 50 - 75 out from reproductive cloning. We could start that process today if we weren't so squeamish.
ML is coming to a head, and we'll potentially have machines that outclass us in basic tasks in 25 - 50 years. Within 200, I'd say the human experiment is at an end.
What then? Either we evolve along with our machines, we become one with the machines, or the machines take over.
We're living in the last stages of the human species right now, and not many people think to contemplate that and integrate it into their worldview.
Climate, space exploration, etc. is all incredibly human-centric. Fighting for resources, defining legacies, ... I mean, it's what we as humans do. One day it'll just suddenly end, and it's probably only a handful of generations until the pieces fall into place.
Just this line makes me skeptical of the rest of your thinking as well... what I've seen of ML application leaves me strongly convinced that every usage of ML will need human supervision and override control. Every case of "can't reach a human to get this corrected" is a call for boycotting / suing to force a human override channel for any automated system.
The "human experiment" is not an experiment, it is the fundamental reality, and no automation will ever truly replace human thoughts plus emotions plus inherent irrational priorities / preferences / biases.
My Kindle books etc. are not visible to my son in the same way. Spatial, in your face, visibility matters in transferring culture.
Then you get over it. They're whip smart and doing things their way, trying to force them into yours probably would not work anyway.
Mostly over it.
Future generations will have a different experience than those in the past. Theirs will be slightly more fair
Aeon https://aeon.co
Undark Magazine https://undark.org
The Conversation https://theconversation.com/global
Curie https://www.tidningencurie.se/en/home/ (based in Sweden)
Edit: actually it upgrades to HTTPS without complaint! Something might be wrong with your software/internet.
That's fine but that will give you an extremely limited vision of the world. The technocratic, slightly anarcho-capitalistic, American-knows-best, social liberal world view.If you choose that way at least go to https://www.project-syndicate.org/, with a little wider spectrum (With actual good economists and not the stenographer of the day) Too bad the redesign is totally crap.
Well I am not sure about that.As it happens with most pop-sci publications the quality has taken a nose-dive.
For example:
> A new thought experiment indicates that quantum mechanics doesn’t work without strange numbers that turn negative when squared.
I am not saying is a "bad" magazine per se, all I am saying is virtuable indistiguinshable from your SciAm, New Scientist and Discover. Some good articles and plenty of fluff.
The level you want is in other places like:
- https://physicstoday.scitation.org/journal/pto (free access to the 73 year archive)
- https://inference-review.com/issues (Ignore the 2014 crackpot articles)
Great article though.
Yuck.
It's easier to get that feeling at a glance when the graphic is increasing left-to-right. With normal conventions the graphic would be decreasing. Which of course, that's what it is doing (and the goal). But the "gut reaction" to a decreasing graph is "things are doing worse". The gut reaction to graph increasing is "things are doing better".
I could be completely off-base, but that's the only reason I can think of to eschew normal axis conventions.
You beat me to it.
Please take your snark elsewhere.
We all create a mental model of time at some point in our life, and then stick to it - often without ever talking about it to anyone.
But the representations vary substantially between people. Many people might have a timeline where the past is on the left and the future is on the right - maybe along the reading direction. But for some, future expands to the left. For others, future expands in front of them while the past is behind them (quite inconvenient).
It can make for a great party conversation to explore each others‘ timelines.
If there are parties, that is.
Additionally the quote below it:
> Mathematicians have been getting closer to their goal of reaching exponent two — meaning multiplying a pair of n-by-n matrices in only n2 steps — but will they ever reach it?
seems particularly odd when the height of those steps is irrelevant in the graphic - if the entire graph was just a flat plane going from n^3 to n^2 it would signify the "best" or at least fastest innovation, the "steppedness" of it and especially steep steps, indicate lags in progress rather than great leaps.