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

21–30 of 63 posts

Re: X X^t can be faster

#21

Post by tptacek »

drlobster wrote: post #10
meisel wrote: post #9

Is this like the Karatsuba algorithm, where it's theoretically faster but not actually faster when run on real hardware? Btw, it's worth noting that if you know that the result will be symmetric (such as is the case for X * X^T), you can make things faster. For example in cuBLAS, cublas*syrk (the variant optimized for when the result is symmetric) IME isn't faster than gemm, so what you can do instead is just do smal…

[flagged]

Let's have more comments from domain experts comparing algorithms in the abstract to cuBLAS, and less like these. Thanks!

If they're wrong to speculate, well, there's a whole paper you can just go skim to find the bit that rebuts them.

Re: X X^t can be faster

#22

Post by FabHK »

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.

The solution to the least squares problem Ax ≈ b is given by x = (A'A)^-1 A'b, but modern solvers never form the matrix product A'A explicitly. Even for the SVD it isn't formed.

Re: X X^t can be faster

#23

Post by qoez »

BryanLegend wrote: post #2

So if an AI company spends $5B on a cluster, is this optimization worth $250m?

Definitely didn't cost that much to solve this particluar problem (that cost is amortized over the lifetime of the clusters existence). Compared to the CO2 to feed academics eating red meat, this is like wind power compared to coal it's way more environmentally friendly.

Re: X X^t can be faster

#24

Post by bee_rider »

meisel wrote: post #9

Is this like the Karatsuba algorithm, where it's theoretically faster but not actually faster when run on real hardware? Btw, it's worth noting that if you know that the result will be symmetric (such as is the case for X * X^T), you can make things faster. For example in cuBLAS, cublas*syrk (the variant optimized for when the result is symmetric) IME isn't faster than gemm, so what you can do instead is just do smal…

The mention 5% improvements and small matrices in the abstract, so my gut says (I haven’t read the actual paper yet) that is probably is a practical-type algorithm.

Re: X X^t can be faster

#25

Post by odo1242 »

meisel wrote: post #9

Is this like the Karatsuba algorithm, where it's theoretically faster but not actually faster when run on real hardware? Btw, it's worth noting that if you know that the result will be symmetric (such as is the case for X * X^T), you can make things faster. For example in cuBLAS, cublas*syrk (the variant optimized for when the result is symmetric) IME isn't faster than gemm, so what you can do instead is just do smal…

It’s faster for matrices of approximately at least ~256x256, though it depends on hardware

Re: X X^t can be faster

#26

Post by toolslive »

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.

Re: X X^t can be faster

#27

Post by pbsd »

meisel wrote: post #9

Is this like the Karatsuba algorithm, where it's theoretically faster but not actually faster when run on real hardware? Btw, it's worth noting that if you know that the result will be symmetric (such as is the case for X * X^T), you can make things faster. For example in cuBLAS, cublas*syrk (the variant optimized for when the result is symmetric) IME isn't faster than gemm, so what you can do instead is just do smal…

Karatsuba is definitely faster than schoolbook multiplication at practical sizes. You presumably mean Strassen.

Re: X X^t can be faster

#29

Post by blobbers »

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

Covariance.

Re: X X^t can be faster

#30

Post by almostgotcaught »

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.

This whole research area should just be renamed to something like approximate computing so that people don't confuse it (and the goals) with classical numerical analysis.

Post reply on HN