XX^t Can Be Faster

Code

• github.com/zhaoolee/garss
  pytorch★ 1,374
• github.com/benearnthof/rxtx
  none★ 2

Abstract

We present RXTX, a new algorithm for computing the product of matrix by its transpose XX^t for X R^n 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 , but also for small matrices including n = 4. The algorithm was discovered by combining Machine Learning-based search methods with Combinatorial Optimization.

Tasks

Reproductions