Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Matrix Multiplication with Half the Multiplications

github.com

Post reply on HN
Print view View original

41–50 of 85 posts

Re: Show HN: Matrix Multiplication with Half the Multiplications

#41

Post by bee_rider »

OJFord wrote: post #20
emacs28 wrote: post #6

Earlier quoted context omitted.

IMHO, for fixed-point MM accelerators, there is no catch, I think it's an overlooked algorithm. It's based on an algorithm by Winograd who coincidentally also proposed another unrelated algorithm that later became very popular for CNN acceleration which would take some visibility away from this other algorithm by Winograd... But that is speculative

LLM hype and this submission in particular keep making me think of a lecturer I had for Topics in Large Dimensional Data Processing , circa 2016: as I recall he was enthusiastically adamant that the most important thing, breakthroughs etc., in years/decades to come was going to be faster matrix operations. Anyway, I'm pretty sure I recognise FIP (not FFIP of course) from that course. I wish I could remember his name,…

Maybe I’m joking, but: our society is just a vehicle for economics at this point, our economy is built around science, our science has mostly been turned into observations about engineering, some time ago we changed all of engineering into differential equations, and differential equations can be solved by discretizing them and doing linear algebra, and most of linear algebra can be done with matrix multiplications (triangular solves and orthonormalizations if you are fancy). All you need is matmul.

Re: Show HN: Matrix Multiplication with Half the Multiplications

#42

Post by Lucasoato »

JohnKemeny wrote: post #31
gizmo686 wrote: post #28

Earlier quoted context omitted.

> I conjecture that for every j > 0 in R, a number n exists so that any two n x n matrices can be multiplied together in O(n^(2+j)) steps. Is this stated correctly? Because it seems almost meaningless as stated. You start with "for every j, there exists an n such that...". That would mean that for the rest of the statement, n and j are constant. So you are just saying that you can multiply constant sized matrices in…

It should simply say: for any j>0 there exists an algorithm multiplying nxn matrices in time O(n^{2+j}).

You are correct, I apologize for the confusion! :)

Re: Show HN: Matrix Multiplication with Half the Multiplications

#43

Post by abetusk »

pclmulqdq wrote: post #16
halflings wrote: post #2

This looks pretty cool! What's the catch? e.g. why isn't this already implemented in accelerators, is it really just a forgotten algorithm, or this has some implications on the cost of building the accelerator or else?

There are a lot of matrix multiplication algorithms out there with a lot of pluses and minuses. It's always a balance of accuracy, runtime, and scaling. This one probably has bad accuracy in floating point.

I don't know why this answer is getting downvoted. This is absolutely correct.

W. Miller has a paper discussing, under conditions of numerical stability, O(n^3) multiplications is necessary [0]. Any algorithm that gets sub cubic runtime for matrix multiplication, like Strassen's or Coppersmith's, must sacrifice some amount of precision or stability.

[0] https://epubs.siam.org/doi/10.1137/0204009

Re: Show HN: Matrix Multiplication with Half the Multiplications

#44

Post by ixaxaar »

jebarker wrote: post #39
ixaxaar wrote: post #12

Man I remembered something similar I had tried working on in 2018, but gave up after all my PhD applications got rejected. https://github.com/ixaxaar/pytorch-dni The concept here goes a bit further and tries to replicate backprop with an external network, arguing that that's probably what the brain actually does.

This feels like a "no free lunch" situation. I would imagine that any time saving in approximating the gradients this way would be lost to needing to train for more iterations due to the loss in gradient accuracy. Is that not the case?

I think that's the reason for its dead end.

However if this is really the biological analogue of credit assignment, this might scale better than training llms from scratch every time. Even if say it could approx gradients to a certain degree given a new network, normal backprop could further tune for a few epochs or so dramatically reducing overall training costs.

Re: Show HN: Matrix Multiplication with Half the Multiplications

#45

Post by tmp8086 »

yorwba wrote: post #15
emacs28 wrote: post #6

Earlier quoted context omitted.

IMHO, for fixed-point MM accelerators, there is no catch, I think it's an overlooked algorithm. It's based on an algorithm by Winograd who coincidentally also proposed another unrelated algorithm that later became very popular for CNN acceleration which would take some visibility away from this other algorithm by Winograd... But that is speculative

On the other hand, if you tried it with floating point, you'd lose significant digits. Since the approach is to sum (a[i] + b[i+1])(a[i+1] + b[i]) and subtract the sums of a[i]a[i+1] and b[i]b[i+1] in the end to get a[i]b[i] + a[i+1]b[i+1], you may be taking the difference of two large values to get a small value, losing precision.

[dead]

Re: Show HN: Matrix Multiplication with Half the Multiplications

#46

Post by waynecochran »

p1esk wrote: post #33
waynecochran wrote: post #30

Earlier quoted context omitted.

The document said it outputs the exact same values as the conventional method. There is no accuracy trade off here.

For floating point? Are you sure?

Opening statement of README

    This repository contains the source code for ML hardware architectures that 
    require nearly half the number of multiplier units to achieve the same 
    performance, by executing alternative inner-product algorithms that trade 
    nearly half the multiplications for cheap low-bitwidth additions, while still 
    producing identical output as the conventional inner product.

Re: Show HN: Matrix Multiplication with Half the Multiplications

#48

Post by gyrovagueGeist »

abetusk wrote: post #43
pclmulqdq wrote: post #16

Earlier quoted context omitted.

There are a lot of matrix multiplication algorithms out there with a lot of pluses and minuses. It's always a balance of accuracy, runtime, and scaling. This one probably has bad accuracy in floating point.

I don't know why this answer is getting downvoted. This is absolutely correct. W. Miller has a paper discussing, under conditions of numerical stability, O(n^3) multiplications is necessary [0]. Any algorithm that gets sub cubic runtime for matrix multiplication, like Strassen's or Coppersmith's, must sacrifice some amount of precision or stability. [0] https://epubs.siam.org/doi/10.1137/0204009

Another relevant paper is: https://epubs.siam.org/doi/10.1137/15M1032168

Re: Show HN: Matrix Multiplication with Half the Multiplications

#49

Post by pk-protect-ai »

skykooler wrote: post #47

I find it fascinating that this is using a process invented in 1968 and hasn't been used for this purpose until now!

Hey, nobody knew what to do with GF(2^x) up until mid last century either... Oh wait, CS was not really a thing almost up until mid last century...

Re: Show HN: Matrix Multiplication with Half the Multiplications

#50

Post by emacs28 »

pclmulqdq wrote: post #16
halflings wrote: post #2

This looks pretty cool! What's the catch? e.g. why isn't this already implemented in accelerators, is it really just a forgotten algorithm, or this has some implications on the cost of building the accelerator or else?

There are a lot of matrix multiplication algorithms out there with a lot of pluses and minuses. It's always a balance of accuracy, runtime, and scaling. This one probably has bad accuracy in floating point.

For everyone discussing the reduced accuracy/numerical stability of the algorithms in floating-point, this is true. But note that the application of the algorithms in the work is explored for fixed-point MM/quantized integer NN inference, not floating-point MM/inference. Hence, there is no reduction in accuracy for that application of it compared to using conventional fixed-point MM.
Post reply on HN