X X^t can be faster
arxiv.org
X X^t can be faster
1–10 of 63 posts
Re: X X^t can be faster
#2So if an AI company spends $5B on a cluster, is this optimization worth $250m?
Re: X X^t can be faster
#3I 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).
Re: X X^t can be faster
#4I 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).
It’s a fairly common operation. The sample covariance of a vector-valued random variable is XX^t/N.
Re: X X^t can be faster
#5So if an AI company spends $5B on a cluster, is this optimization worth $250m?
Don't think so. This is an optimization on multiplying a matrix times its own transpose, not for generic matrix multiplication.
Re: X X^t can be faster
#6I 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).
It’s pretty fundamental in a variety of multivariate statistical methods. If the rows of X are multi variate observations, then XX’ is the Gram matrix (of dot products). This can be used in clustering and regression. If the columns of X are (centered) multivariate observations, then XX’ is a scalar multiple of the sample covariance matrix. This is used in PCA.
But in large scale applications you may not want to store XX’ but instead are interested in computing products of the form XX’ v on the fly.
Re: X X^t can be faster
#7I 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).
Could be useful when doing an SVD as well (although, really, you don’t want X’X but X’Xv for some vector…).
Re: X X^t can be faster
#8I wish they could have modeled memory cache movements as well, somehow. It would have made the analysis more difficult but often these large matrix algorithms live or die by how cache-friendly the memory access patterns are.
Splitting into 4x4 blocks is typically very nice, though. Maybe it doesn’t matter so much to practical runtime.
Re: X X^t can be faster
#9Is 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 smaller multiplications that fill in one of the two triangles piece by piece, and then copy that triangle to the other one.
Re: X X^t can be faster
#10Is 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]