Fast rectangular matrix multiplication and some applications

We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary dimensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results: (i) we decrease from O(n(2) + n(1+o(1)) log q) to O(n(1.9998) + n(1+o(1)) log q) the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor 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; (iii) we decrease from O(m(1.575)n) to O(m(1.5356)n) the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.