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

X X^t can be faster

arxiv.org

Post reply on HN
Print view View original

31–40 of 63 posts

Re: X X^t can be faster

#31

Post by wizzwizz4 »

constantcrying wrote: post #19
ttoinou wrote: post #16

Are there researchers interested in accelerating these algorithms while also keeping the maximum accuracy of the results ? This and others optimizations are trading less multiplication for more additions, but from the little I know, on floating point additions and subtractions are risky precision wise, while multiplications are harmless. Also using FMA fused multiply add operations would be beneficial.

The question of stability of the algorithm is interesting, the paper does not seem to discuss it though. You are correct that we should expect the algorithms to deliver different results. >This and others optimizations are trading less multiplication for more additions, but from the little I know, on floating point additions and subtractions are risky precision wise, while multiplications are harmless. Certainly not…

Different orders of magnitude aren't a problem when multiplying floats, because the order-of-magnitude portion gets translated into addition of exponents.

They're a problem with fixed point: might you have been thinking of that?

Re: X X^t can be faster

#32

Post by saagarjha »

almostgotcaught wrote: post #30
ttoinou wrote: post #16

Are there researchers interested in accelerating these algorithms while also keeping the maximum accuracy of the results ? This and others optimizations are trading less multiplication for more additions, but from the little I know, on floating point additions and subtractions are risky precision wise, while multiplications are harmless. Also using FMA fused multiply add operations would be beneficial.

> while also keeping the maximum accuracy of the results All of these papers/algos are for the ML hype-train. ML algos are approximate anyway so no one cares about absolute accuracy, only the precision of the overall pipeline (class labels shouldn't change, at least not too much). Consider that very many papers/techniques quantize down to 8 or even 4 bits (yes sometimes even during training) for the purposes of perf.…

Surely nobody is tiling 4x4 blocks for ML training

Re: X X^t can be faster

#33

Post by Dylan16807 »

wizzwizz4 wrote: post #31
constantcrying wrote: post #19

Earlier quoted context omitted.

The question of stability of the algorithm is interesting, the paper does not seem to discuss it though. You are correct that we should expect the algorithms to deliver different results. >This and others optimizations are trading less multiplication for more additions, but from the little I know, on floating point additions and subtractions are risky precision wise, while multiplications are harmless. Certainly not…

Different orders of magnitude aren't a problem when multiplying floats , because the order-of-magnitude portion gets translated into addition of exponents. They're a problem with fixed point: might you have been thinking of that?

We're not looking at instructions in a vacuum. No matter what you have both multiplications and additions happening.

So they're making a point that if you apply more multiplications before the inevitable addition, you are likely increasing the danger levels of that addition.

Re: X X^t can be faster

#34

Post by Bootvis »

Scene_Cast2 wrote: post #3

I can't name any applications off the top of my head, other than iterative matrix multiplication for approximate eigenvector finding in square matrixes. But I don't know what's actually used for finding eigenvectors (or other decompositions for that matter).

I expect this algorithm or similar to work for X^tX as well. Fun fact, that operation is common enough that a trading firm was named after it: XTX Markets.

Re: X X^t can be faster

#35

Post by wizzwizz4 »

Dylan16807 wrote: post #33
wizzwizz4 wrote: post #31

Earlier quoted context omitted.

Different orders of magnitude aren't a problem when multiplying floats , because the order-of-magnitude portion gets translated into addition of exponents. They're a problem with fixed point: might you have been thinking of that?

We're not looking at instructions in a vacuum. No matter what you have both multiplications and additions happening. So they're making a point that if you apply more multiplications before the inevitable addition, you are likely increasing the danger levels of that addition.

Oh, if one of the multiplications yields a positive number, and another yields a negative number of similar magnitude? That makes sense; I forgot linear spaces were over fields.

Re: X X^t can be faster

#36

Post by almostgotcaught »

saagarjha wrote: post #32
almostgotcaught wrote: post #30

Earlier quoted context omitted.

> while also keeping the maximum accuracy of the results All of these papers/algos are for the ML hype-train. ML algos are approximate anyway so no one cares about absolute accuracy, only the precision of the overall pipeline (class labels shouldn't change, at least not too much). Consider that very many papers/techniques quantize down to 8 or even 4 bits (yes sometimes even during training) for the purposes of perf.…

Surely nobody is tiling 4x4 blocks for ML training

Why surely? Eg on GPU style chips today you'd tile to warpsize (or half or something like that) to target warp cooperative primitives (so called tensor cores). On AMD and NV that's like 16x16 or 32x32 depending on the data type. That's not that far from 4x4 and it's not like all chips in the world have 32-lane warps. Anyway if a trick is good enough and people start trying to shoehorn it into everything (not saying this one is) then the next gen (or the one after that or after) will just have units to support the trick (it's an expensive way to gain ground on mlperf rankings).

Re: X X^t can be faster

#37

Post by jerf »

constantcrying wrote: post #20
Scene_Cast2 wrote: post #3

I can't name any applications off the top of my head, other than iterative matrix multiplication for approximate eigenvector finding in square matrixes. But I don't know what's actually used for finding eigenvectors (or other decompositions for that matter).

I think one particularly interesting result is that superior algorithms for numerical linear algebra exist at all and can be found by artificial intelligence. XX^T is the matrix of all piecewise dot products of vectors in X and as others have pointed out there are legitimate applications. Another one being e.g. transforming an undetermined linear system into a least squares problem.

Google put something out like this recently too. The original is https://deepmind.google/discover/blog/alphaevolve-a-gemini-p..., but it's sort of buried in there. Here's the YouTube video that introduced it to me, forwarded to the spot where the host talks about the improved 4x4 matrix multiplication algorithm: https://www.youtube.com/watch?v=sGCmu7YKgPA&t=396s It's only a slight tweak, but it's a slight tweak to something pretty highly studied and still impressive.

Re: X X^t can be faster

#38

Post by jerf »

toolslive wrote: post #26

as a general tip: X^-1 doesn't mean you have to inverse the matrix. It's often a notational shorthand for "you can solve the system". Same remark for X^t. It doesn't mean you have to build a new matrix. It just means you have to use the one you have in a different way. I've have seen this being butchered by scientists and then they complain their performance sucks.

Even computer programmers can get it wrong, and even reify the wrongness into interview questions. The correct answer to the common question of "how do you reverse an array" is that you don't reverse it. You read it backwards. Details vary from language to language; languages with iterators can find this particularly easy. But this is often not the "correct" answer according to the interviewer.

In the end, all data structures are functions. The academic applications of that may make your eyes glaze over, but the practical application is that if you want a reversed array/tree/etc., you just need the reading/iteration "function" for the array to return the data as if it was reversed. A matrix can be "transposed" just by reading its transpose. (Caching or other consequences may result in you choosing to manifest it in memory anyhow, but if it was stored cleverly in the first place, or you're only going to read it once anyhow such that using it once is as expensive as reading it once to reconstruct it anyhow, then there's no reason to.) An array can be randomly permuted simply by wrapping the read function with a permutation on the index, it need not be manifested in memory. etc.

Re: X X^t can be faster

#39

Post by kazinator »

Under multiplication, rows go into columns and all that. So if we transpose things, rows are being dot-producted with (what were originally) rows:

  [ a b ] [ a c ] = [ (a b) . (a b)  (a b) . (c d) ] = [   |(a b)]^2     (a b) . (c d) ]
  [ c d ] [ b d ]   [ (c d) . (a b)  (c d) . (c d) ]   [ (c d) . (a b)      |(c d)|^2  ]
Down the diagonal we have squared norms of (a b) and (c d) which is interesting and could somehow be used.

We also have repeated values between the upper and lower triangle because (a b) . (c d) is the same as (c d) . (a b): the dot product commutes.

Whereas just squaring the matrix:

  [ a b ] [ a b ] = [ (a b) . (a c)  (a b) . (b d) ]
  [ c d ] [ c d ]   [ (c d) . (a c)  (c d) . (b d) ]
all four dot products are unique.

So right of the bat, we can find interesting things about X X^t without going deep, and an obvious shortcut.

Re: X X^t can be faster

#40

Post by kazinator »

jerf wrote: post #38
toolslive wrote: post #26

as a general tip: X^-1 doesn't mean you have to inverse the matrix. It's often a notational shorthand for "you can solve the system". Same remark for X^t. It doesn't mean you have to build a new matrix. It just means you have to use the one you have in a different way. I've have seen this being butchered by scientists and then they complain their performance sucks.

Even computer programmers can get it wrong, and even reify the wrongness into interview questions. The correct answer to the common question of "how do you reverse an array" is that you don't reverse it. You read it backwards. Details vary from language to language; languages with iterators can find this particularly easy. But this is often not the "correct" answer according to the interviewer. In the end, all data s…

The "invert binary tree" interview question can be solved by swapping the accessors of the node type:

  tmpfn = tree.left
  tree.left = tree.right
  tree.right = tmpfn
Now when tree.left(node) is applied, it returns the right child, and vice versa. All traversals use the accessors, QED.
Post reply on HN