$XX^{t}$ Can Be Faster

我们提出了一种新的算法 RXTX，该算法用于计算矩阵与其转置的乘积 $XX^{t}$。RXTX 比现有最先进的方法减少了 5% 的乘法和加法运算，并且即使在矩阵 $X$ 的规模较小时也能实现加速。该算法是通过结合基于机器学习的搜索方法与组合优化技术发现的。

论文试图解决矩阵乘法中的计算效率问题，特别是如何更高效地计算矩阵与其转置的乘积XX^T。这是一个在科学计算和机器学习中常见的基础问题，但通过减少乘法和加法操作来进一步优化计算效率是一个持续探索的方向。

论文的关键思路是结合机器学习搜索方法与组合优化技术，提出了一种新的算法RXTX。该算法能够以比现有最佳方法少5%的乘法和加法操作完成XX^T的计算。相比当前领域的研究状况，这种方法不仅在理论上减少了计算复杂度，还在小规模矩阵上展示了实际加速效果，这是传统优化方法较少关注的领域。

论文的主要亮点包括：1) RXTX算法在小规模矩阵上也表现出显著加速效果；2) 使用了机器学习与组合优化相结合的方法来发现新算法，这是一种跨学科的研究方式；3) 实验部分详细对比了不同规模矩阵下的性能提升，并验证了算法的普适性。目前尚不清楚是否有开源代码，但值得继续研究的是如何将类似方法扩展到其他线性代数运算中。

近期相关研究包括：1) Strassen算法及其变体在矩阵乘法中的应用；2) 利用张量分解优化矩阵运算的研究（例如“Tensor-based Optimization for Matrix Multiplication”）；3) 基于深度强化学习自动发现数学算法的工作（如“AlphaTensor: Discovering Novel Algorithms with Deep Reinforcement Learning”）。这些研究共同推动了高效算法设计的边界。