On practical algorithms for accelerated matrix multiplication

AbstractWe present several bilinear algorithms for the acceleration of multiplication of n X n matrices that are superior to both the classical and Strassen's algorithm for moderate n (starting with n = 20). The Bini-Lotti result on the weak stability of bilinear algorithms applies to these algorithms. We present them in two equivalent versions, bilinear and trilinear. We also apply one of these algorithms over finite fields (or rings) of constants. Surprisingly, this enables us to decrease the bilinear complexity of n X n matrix multiplication (for 20 ⩽ n ⩽ 1020) below the current record upper bound for the same computation over the infinite fields of complex, real, or rational numbers