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

11–20 of 85 posts

Re: Show HN: Matrix Multiplication with Half the Multiplications

#11

Post by Someone »

barfbagginus wrote: post #4

This readme does a really poor job of explaining what the improvement is or how they drop half the multiplications. What is the Big O run time on this? Is this shifting the known best bounds? And the diagrams are chaotic and don't really explain anything about why this approach is fast or good. The result is that I'm reluctant to even click-through to the PDF. If you want to improve the project credibility please con…

> What is the Big O run time on this?

The claim is they’re dropping half the multiplications, so it isn’t doing anything for Big O.

> If you want to improve the project credibility please consider being honest and open about what is actually going on and giving some clear explanations and illustrations,

The math explaining how to halve the number of multiplications in the paper (https://arxiv.org/abs/2311.12224) isn’t hard to understand.

You only have to read formulas 2 (traditional matrix multiplication) and 3 to 6.

I think it’s clear it does do what’s being advertised, halving the number of multiplications at the cost of lots of extra additions/subtractions.

They then go on to better vectorize that algorithm. That, as is usual for that, gets looking messy soon.

My main concern would be numerical stability.

Re: Show HN: Matrix Multiplication with Half the Multiplications

#12

Post by ixaxaar »

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.

Re: Show HN: Matrix Multiplication with Half the Multiplications

#13

Post by emacs28 »

Someone wrote: post #11
barfbagginus wrote: post #4

This readme does a really poor job of explaining what the improvement is or how they drop half the multiplications. What is the Big O run time on this? Is this shifting the known best bounds? And the diagrams are chaotic and don't really explain anything about why this approach is fast or good. The result is that I'm reluctant to even click-through to the PDF. If you want to improve the project credibility please con…

> What is the Big O run time on this? The claim is they’re dropping half the multiplications, so it isn’t doing anything for Big O. > If you want to improve the project credibility please consider being honest and open about what is actually going on and giving some clear explanations and illustrations, The math explaining how to halve the number of multiplications in the paper ( https://arxiv.org/abs/2311.12224 ) is…

Thanks, good summary. Regarding numerical stability, the application is for fixed-point arithmetic, and therefore numerical stability is not an issue (the result is identical compared to using the conventional inner-product)

Re: Show HN: Matrix Multiplication with Half the Multiplications

#14

Post by yorwba »

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.

I'm not seeing the connection. This work is about low-level optimization of matrix multiplication. The repo you linked seems to be about replacing back-propagated gradients with a cheaper estimate. What's the similarity you see between these two?

Re: Show HN: Matrix Multiplication with Half the Multiplications

#15

Post by yorwba »

emacs28 wrote: post #6
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?

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.

Re: Show HN: Matrix Multiplication with Half the Multiplications

#16

Post by pclmulqdq »

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.

Re: Show HN: Matrix Multiplication with Half the Multiplications

#17

Post by ixaxaar »

yorwba wrote: post #14
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.

I'm not seeing the connection. This work is about low-level optimization of matrix multiplication. The repo you linked seems to be about replacing back-propagated gradients with a cheaper estimate. What's the similarity you see between these two?

Correct, I think I mistook it as "use a small neural net to approximate matrix multiplication" instead it seems as "use cheaper replacements of matrix mul without much acc loss".

Wellll that means I can give dni another try :D

Re: Show HN: Matrix Multiplication with Half the Multiplications

#18

Post by lupire »

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?

It's not just a software algorithm. It's a hardware architecture optimization. To benefit, you have to build hardware that matches the dimensions of the algorithm. That's an expensive commitment.

Re: Show HN: Matrix Multiplication with Half the Multiplications

#19

Post by VogonPoetry »

hackyhacky wrote: post #8
mariocesar wrote: post #5

Earlier quoted context omitted.

It´s actually fairly clear

Not to everyone. If it's clear to you, you could helpfully explain it.

This is an analogy. a^2 - b^2 = aa - bb. This can be factored to (a+b)(a-b). In the first expression there are two multiplies, in the factored version there is only one.

However, from a numerical analysis / accuracy standpoint, evaluating the factored expression can result in loss of precision in the result when a is close to b. This is especially true if you repeatedly and sequentially do a lot of these operations. Loss of precision can be a problem in numeral modeling (like climate simulation) -- long term predictions diverge.

Given that there is a drive to use greatly reduced precision in ML engines, loss of precision might have an effect on how a model performs. Then again, it might not. I haven't read a lot of papers on ML, but I don't recall seeing ones that try to quantify how sensitive a model is to error propagation. (I am making a distinction between tests where the precision is reduced to see where it breaks down v.s. calculating / understanding what the error level actually is in a model)

Re: Show HN: Matrix Multiplication with Half the Multiplications

#20

Post by OJFord »

emacs28 wrote: post #6
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?

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, I believe he left academia after my year and went to work in industry, I'd just be curious to see what he's up to now. I'm not saying it was a particularly novel or prescient comment/attitude, we may not have had quite such ML hype but certainly 'big data' was all the rage at the time, it's just something that's stuck in my mind. One of those areas I always meant to study more, just realistically probably never had the mathematical chops for and certainly those I did have atrophied.

Post reply on HN