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

11–20 of 63 posts

Re: X X^t can be faster

#11

Post by optimalsolver »

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…

>where it's theoretically faster but not actually faster when run on real hardware

Aka a galactic algorithm:

https://en.wikipedia.org/wiki/Galactic_algorithm

Re: X X^t can be faster

#12

Post by thrance »

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…

They tested it against BLAS primitives and found theirs to be faster, in hardware.

Re: X X^t can be faster

#13

Post by thrance »

optimalsolver wrote: post #11
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…

>where it's theoretically faster but not actually faster when run on real hardware Aka a galactic algorithm: https://en.wikipedia.org/wiki/Galactic_algorithm

I feel like a galactic algorithm is slow even theoretically, unless you work with out-of-this-world data.

Whereas many algorithms are theoretically fine for real data but don't make good use of cache, or instruction sets...

Re: X X^t can be faster

#14

Post by meisel »

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]

I figured it might, but I think that this is a top of mind question for people and would be nice to make clear in the comments of the post too. So often there’s some theoretical improvement on multiplication that isn’t actually practical. Regardless, they don’t seem to have posted results for CUDA, which is arguably more important than CPU multiplication which is what they tried

Re: X X^t can be faster

#16

Post by ttoinou »

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.

Re: X X^t can be faster

#17

Post by tsurba »

meisel wrote: post #14
drlobster wrote: post #10

Earlier quoted context omitted.

[flagged]

I figured it might, but I think that this is a top of mind question for people and would be nice to make clear in the comments of the post too. So often there’s some theoretical improvement on multiplication that isn’t actually practical. Regardless, they don’t seem to have posted results for CUDA, which is arguably more important than CPU multiplication which is what they tried

Probably why they tried to address it in the abstract already

Re: X X^t can be faster

#18

Post by qoez »

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…

Since this is 2x2 there's simd instructions that can do this (or with two simd dot products) both on CPU and inside each GPU core. So with current hardware you won't beat writing this out manually.

Re: X X^t can be faster

#19

Post by constantcrying »

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 true. In general different orders of magnitude are a problem. With multiplication and division these are more serve problems, as they lead to greater changes in magnitude, although even that is a generalization.

Re: X X^t can be faster

#20

Post by constantcrying »

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.

Post reply on HN