$X{X}^t$ Can Be Faster

Abstract

We present RXTX, a new algorithm for computing the product of matrix by its transpose $X{X}^t$ for $X\in {\mathbb{R}}^{n\times m}$. RXTX uses $5\%$ fewer multiplications and $5\%$ fewer operations (additions and multiplications) than State-of-the-Art algorithms. Note that the accelerations not only holds asymptotically for large matrices with $n\to \infty$, but also for small matrices including $n=4$. The algorithm was discovered by combining Machine Learning-based search methods with Combinatorial Optimization.

improved presentation