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

31–40 of 85 posts

Re: Show HN: Matrix Multiplication with Half the Multiplications

#31

Post by JohnKemeny »

gizmo686 wrote: post #28
Lucasoato wrote: post #25

If you're interested in the mathematical theory behind sub-cubic algorithms for matrix multiplications, you can start from here: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith... 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. (Now proven for for 2+j = w = 2.3728596, or j > 0.3728596)

> 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}).

Re: Show HN: Matrix Multiplication with Half the Multiplications

#32

Post by JohnKemeny »

roflmaostc wrote: post #27
abeppu wrote: post #26

Earlier quoted context omitted.

Predicting that this holds for any j > 0 seems rather bold. Would you care to share your intuition why you think that's the case?

Two matrices with size NxN each can be multiplied naively with the schoolbook algorithm in O(N^3). It's clear that the algorithm needs at least O(N^2) because to access each element of the matrices once, you need a double for loop, which is O(N^2). for i in rows for j in cols # do something with element matrix1 [i, j], matrix2[i, j],... so it has to be j >= 0

His question was: what is the reasoning behind there existing an algorithm running in time n^2+epsilon for really small epsilon.

Re: Show HN: Matrix Multiplication with Half the Multiplications

#33

Post by p1esk »

waynecochran wrote: post #30
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.

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?

Re: Show HN: Matrix Multiplication with Half the Multiplications

#34

Post by [deleted] »

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…

[deleted]

Re: Show HN: Matrix Multiplication with Half the Multiplications

#36

Post by eigenket »

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…

> 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?

Without wishing to sound elitist I, I don't understand the point of this comment at all. If you don't understand Big O notation enough to know that "half the multiplications" doesn't change it then why are you even asking about it?

Re: Show HN: Matrix Multiplication with Half the Multiplications

#37

Post by pk-protect-ai »

michelpp wrote: post #29

This is very cool and a real interesting read! For those in the comments confused about how this is better, the paper is talking about synthesizing matrix multiplication pipelines in hardware, like an FPGA or ASIC. On a CPU or GPU you won't notice because adds and multiplications take the same amount of time generally, but multiplication units takes up many more transistors, so if you can reduce the circuit complexit…

> By scaling the numbers first by taking the log, multiplication becomes addition and addition becomes x + log1p(exp(y - x)).

Isn't this the same approach as in GF(2^x), which has been in use for decades? The only limitation that comes to mind is the field size.

Re: Show HN: Matrix Multiplication with Half the Multiplications

#38

Post by adastra22 »

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?

I’ve only glanced at it so someone correct me if I’m wrong, but IIUC this is not a replacement for matrix multiplication but rather an approximation that only gives decent-ish results for the types of linear systems you see in AI/ML. But for that use case it is totally fine?

Re: Show HN: Matrix Multiplication with Half the Multiplications

#39

Post by jebarker »

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?

Re: Show HN: Matrix Multiplication with Half the Multiplications

#40

Post by pclmulqdq »

waynecochran wrote: post #30
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.

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

The paper cited is about hardware, where there is no accuracy tradeoff because you control the numerical precision completely and use fixed point. In a software implementation, neither is true. There is no chance that you will get the exact same values out of this method that you do out of other FP matmuls.
Post reply on HN