[HN Gopher] New breakthrough brings matrix multiplication closer...
___________________________________________________________________
New breakthrough brings matrix multiplication closer to ideal
Author : bertman
Score : 152 points
Date : 2024-03-07 16:11 UTC (1 days ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| Someone wrote:
| As expected: closer, but not much closer. FTA: _"we give a new
| bound of o <2.371866 [...]. Our result breaks the lower bound of
| 2.3725"_
|
| AFAIK the current theoretical lower bound still is 2, so that's
| only 600-ish more such steps to get there.
|
| On the positive side, I don't think anybody believes that 2 even
| remotely is a tight bound.
| bravura wrote:
| What is positive about the best-case scenario being worse than
| we thought?
| Filligree wrote:
| It would mean our best algorithms are closer to optimal than
| otherwise, which at least says positive things about our
| researchers.
| JohnKemeny wrote:
| Currently: 2.37187.
|
| Not remotely close to 2.
|
| What is the limit you would set for remotely close to 2?
| eigenket wrote:
| The previous state of the art was 2.371866, this improvement
| brings it down by 0.000314. If you're moving increments that
| small 2 looks quite far away.
| light_hue_1 wrote:
| > AFAIK the current theoretical lower bound still is 2 ... I
| don't think anybody believes that 2 even remotely is a tight
| bound.
|
| It's not "still". It's trivial to prove that 2 is the lowest
| possible value. Simply because you can't even read all the
| inputs in less than n^2 operations. So it's a tight lower bound
| for sure.
| cwillu wrote:
| It's not a tight lower bound unless it's proven that no
| greater value could be a lower bound, and that's very much an
| open problem if I understand correctly.
| Asraelite wrote:
| What's the difference between doing that and just straight
| up proving what the exact value is?
| Someone wrote:
| It cannot be harder, and could be a lot easier.
|
| Lots (well, relatively lots; this isn't a research area
| with millions of practitioners) of people must have been
| looking at that problem ever since Strassen showed the
| exact value is less than 3 in 1969
| (https://en.wikipedia.org/wiki/Strassen_algorithm), and
| there hasn't been progress on moving that needle, so I
| doubt it's even remotely easy, though.
| seanhunter wrote:
| Depending on the nature of the problem and the proof
| technique, sometimes it can be (from a little to much)
| easier to prove something is no greater than or no less
| than a certain bound than proving what exactly it is. For
| example it's trivial to prove using triangles that the
| square root of two is somewhere between 7/5 and 3/2 but
| proving exactly the value of root two is quite a lot
| harder.
| pletnes wrote:
| Indeed - a classic <<upping the game>> is to prove two
| bounds, then determine an exact value because you somehow
| get the bounds to intersect.
| https://en.wikipedia.org/wiki/Squeeze_theorem?wprov=sfti1
| burnished wrote:
| Hell yeah, squeeze theorem! I was so enchanted when I
| first learned this one that everyone I knew also learned
| about the squeeze theorem.
|
| Sorry, nothing substantial to add, I just got excited
| about it again
| layer8 wrote:
| To prove the exact value, you generally have to provide
| an algorithm that (provably) fulfills that value, and
| also prove that no other algorithm can possibly do better
| ajross wrote:
| It's very distressing to see this insightful and helpful
| comment[1] grayed out because of a pedandic argument about
| what "tight" means. The HN community used to be so much
| better than this.
|
| [1] I'm sure everyone who clicked the downvote button thought
| it was obvious, but not everyone here has that level of
| intuition about big-O analysis. This isn't a math forum,
| we're all hackers here, right?
| sudosysgen wrote:
| Who knows? It could be n^2 log n, which when we're playing with
| the exponent basically is n^2.
| sevagh wrote:
| Can anybody who knows or understands better, how applicable is
| this new technique to being used in a GEMM implementation in a
| BLAS library in mainstream numerical libraries?
| klyrs wrote:
| It's been a great many years since I've touched this stuff but
| two rules of thumb probably haven't changed in the meantime:
|
| 1. in general, algorithms tend to slow down on small problems
| in exchange for the asymptotic speedup -- so you probably don't
| want to use this algorithm for anything that fits in memory (or
| perhaps the solar system)
|
| 2. in specific, asymptotically fast matrix multiplication tend
| to be numerically unstable. So you probably don't want to use
| this algorithm unless you're working with infinite precision.
| sdenton4 wrote:
| These tend to be galactic algorithms. Furthermore, I don't know
| that they do any work involving parallelism, or considering the
| narrowing gap between time needed for addition vs
| multiplication - typically only multiplies are counted.
| infradig wrote:
| I know nothing but read the article. These improvements are
| about analytic solutions and have no practical use. At least
| that's what it said.
| dang wrote:
| Related ongoing thread:
|
| _New Bounds for Matrix Multiplication: From Alpha to Omega_ -
| https://news.ycombinator.com/item?id=39630949 - March 2024 (22
| comments)
| slmjkdbtl wrote:
| What will happen to the world if we found a way to calculate
| matrix multiplication that uses 0s time and 0 resource?
| vouaobrasil wrote:
| Well, since matrix multiplication also contains regular
| multiplication (multiplication of 1x1 matrices) and addition
| (multiplication of 2x2 matrices of the form
|
| 1 x
|
| 0 1
|
| Then you can do basic arithmetic with 0 resources.
| faceplanted wrote:
| Well, 0 isn't really possible, but assuming you're just asking
| "What would the impact be on the world if me made matrix
| multiplication trivial" in the same way that people ask what
| making a room temperature superconductor would do for us.
|
| The answer is quite a lot in computing terms, matrix
| multiplication is used everywhere, most notably at the moment,
| neural networks use almost entirely matrix multiplication, so
| their power consumption would drop almost entirely, and
| correspondingly we could scale them up enormously, your phone
| could run GPT5 locally as long as it had the storage space,
| high fidelity computer vision everywhere would become trivial,
| Google Glass might even become useful.
|
| Previously very limited engineering simulations like weather
| forecasting would improve by leaps and bounds.
|
| Basically everything would change all at once because we'd have
| effectively made p = np, any problem you can turn into a matrix
| multiplication (so basically most maths problems) would become
| solvable.
|
| At the moment we use hardware like GPU's and TPU's in the case
| of AI to make matrix multiplication much quicker and the
| companies that make them have recently become some of the
| biggest in the world because it's so important to everything we
| do now to be able to multiply matrices quickly.
| dgacmu wrote:
| We would have broken some fundamental laws, because to multiply
| two n x n matrices, it takes n^2 time to write down the answer.
|
| So the better question to ask is: What happens if we find a
| practical algorithm (and a theoretical approach) that lets us
| do matmul in only n^2 time? And the answer is - well, some
| important things get faster and we're able to solve larger
| problems in things like optimization, simulation, deep
| learning, etc., or save a lot of time and money doing them.
|
| We'd go from about n^2.8 to n^2, which, let's say for a 1M x 1M
| matrix, is about 64k times faster. That's really nice. But the
| speedup for more common sized matrices is smaller - 256x faster
| for a 1024x1024 matrix.
|
| It would be a very important thing that would cause us to re-
| examine the use of matrix multiplication as a primitive for
| more things, and would have very important practical
| implications - and at the same time, would also kind of look
| like 15 years of Moore's law, not that we're guaranteed to have
| 15 years of that. So, "big" but not necessarily "totally
| reshape the world".
| hansvm wrote:
| Exact mat-mat-mul is fine and all (congrats to the authors), but
| I'm much more interested in approximate mat-vec-mul.
| Specifically:
|
| (1) Pre-process an nxn matrix m into f(m). Any transformation is
| allowed, but to work well on all matrices and input vectors it's
| not possible to rely solely on compression techniques (random
| sampling, low-rank+sparse approximation, ...).
|
| (2) Compute an approximation of m@v via some computation g(f(m),
| v) in less than O(n^2) time (ideally being able to trade off
| accuracy for speed). Above a certain performance threshold, this
| necessarily means you only use a part of f(m) for any one vector
| v.
|
| There's a zero-error O(n) solution that computes a hash table of
| all possible matrix-vector products, so I'll be picky and add the
| constraint that pre-processing time/space are "reasonable".
| phkahler wrote:
| I suspect the limit will be O(n^2xlog(n)). It might also be
| easier to work out the complexity by considering the size of the
| problem to be the number of elements in a matrix instead, so
| O(nlog(n)) which would then be equivalent to O(n^2xlog(n)) using
| the n we use today. I also find it interesting that the current
| exponents seem to be closing in on 2+1/e.
___________________________________________________________________
(page generated 2024-03-08 23:02 UTC)