$XX^{t}$ Can Be Faster
This work addresses a fundamental computational bottleneck in linear algebra, with potential applications in machine learning and data analysis, though it appears incremental as it builds on existing methods.
The paper tackles the problem of computing the matrix product $XX^{t}$ more efficiently, resulting in RXTX, which uses 5% fewer multiplications and 5% fewer total operations than state-of-the-art algorithms, with improvements applicable to both large and small matrices.
We present RXTX, a new algorithm for computing the product of matrix by its transpose $XX^{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 \rightarrow \infty$, but also for small matrices including $n = 4$. The algorithm was discovered by combining Machine Learning-based search methods with Combinatorial Optimization.