Fast rectangular matrix multiplication and applications

First we study asymptotically fast algorithms for rectangular matrix multiplication. We begin with new algorithms for multiplication of an n x n matrix by an n x n(2) matrix in arithmetic time O(n(omega)), omega = 3.333953..., which is less by 0.041 than the previous record 3.375477.... Then we present fast multiplication algorithms for matrix pairs of arbitrary dimensions, estimate the asymptotic running time as a function of the dimensions, and optimize the exponents of the complexity estimates. For a large class of input matrix pairs, we improve the known exponents. Finally we show three applications of our results: (a) we decrease from 2.851 to 2.837 the known exponent of the.work bounds for fast deterministic (NC) parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n x n matrix, as well as for the solution to a nonsingular linear system of n equations, (b) we asymptotically accelerate the known sequential algorithms for the univariate polynomial composition mod x(n), yielding the complexity bound O(n(1.667)) versus the old record of O(n(1.688)), and for the univariate polynomial factorization over a finite field, and (c) we improve slightly the known complexity estimates for computing basic solutions to the linear programming problem with n constraints and n variables. (C) 1998 Academic Press.