6 ms·
X X^t can be faster
- BryanLegend 1y agoSo if an AI company spends $5B on a cluster, is this optimization worth $250m?
- disofu234 1y agoDon't think so. This is an optimization on multiplying a matrix times its own transpose, not for generic matrix multiplication.
- qoez 1y agoDefinitely 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.
- Scene_Cast2 1y agoI 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).
- TimorousBestie 1y agoIt’s a fairly common operation. The sample covariance of a vector-valued random variable is XX^t/N.
- bee_rider 1y agoCould be useful when doing an SVD as well (although, really, you don’t want X’X but X’Xv for some vector…).
- vqv 1y agoIt’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.
- adgjlsfhk1 1y agogenerally good implementations use QR instead
- constantcrying 1y agoI 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.
- FabHK 1y agoThe 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.
- jerf 1y agoGoogle put something out like this recently too. The original is https://deepmind.google/discover/blog/alphaevolve-a-gemini-powered-coding-agent-for-designing-advanced-algorithms/ 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 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.
- blobbers 1y agoCovariance.
- Bootvis 1y agoI 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.
- TimorousBestie 1y agoI 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.
- grumpymuppet 1y agoI wish cache analysis was exposed more broadly everywhere. Everyone I deal with seems to understand and know how to think about it, but best practices seem to be wrapped up in a lot of heuristics. I am aware of being able use hardware counters for profiling systems, but the more fine-grained exposure of what's happening at a lower level seems to be just hidden... Or I haven't found the right reference resource yet.
- zacmps 1y agoDo you know any resources for learning these heuristics?
- meisel 1y agoIs 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.
- drlobster 1y ago[flagged]
- meisel 1y agoI 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
- tsurba 1y agoProbably why they tried to address it in the abstract already
- tptacek 1y agoLet'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.
- optimalsolver 1y ago>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 https://en.wikipedia.org/wiki/Galactic_algorithm
- deleted 1y ago[deleted]
- ttoinou 1y agoAre 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.
- constantcrying 1y agoThe 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.
- wizzwizz4 1y agoDifferent 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?
- Dylan16807 1y agoWe'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.
- wizzwizz4 1y agoOh, 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.
- toolslive 1y agoas 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.
- jerf 1y agoEven 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.
- kazinator 1y agoThe "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.
- saagarjha 1y agoAs I mentioned the last time you brought this up, one does not always have the luxury of “reading in reverse order” or “reading the transpose”. If your library/OS/hardware don’t give you an option or only work effectively in one representation then you have to actually do the work.
- selimthegrim 1y agoI guess the news is the “for small sizes” part
- kazinator 1y agoUnder 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.
- jethkl 1y agohow helpful was ai for this? The paper is light on details, but it says the agent was used to generate a kind of seed set (rank-1 bilinear products) that were then fed into the subsequent steps. Evidently this idea succeeded. Curious if anyone here has insight into if this is a common technique, how this agent's output would compare to random or a simple heuristic that attempts the same. Also interested to see how the training objective gets defined since the final task is a couple of steps downstream from what the agent generates.