Fast rectangular matrix multiplication and applications (Q1271174): Difference between revisions

\textit{D. Coppersmith} and \textit{S. Winograd} [J. Symb. Comput. 9, No. 3, 251-280 (1990; Zbl 0702.65046)] published an algorithm for \(n \times n\) matrix multiplication requiring \(O(n^\omega)\) arithmetic operations, with \(\omega< 2.376\). The present authors extend the method to multiplication of an \(n\times n\) matrix by an \(n\times n^2\) matrix requires \(O(n^\omega)\) arithmetic operations, with \(\omega< 3.334\), less than the previous record by 0.041. After this, the method is extended to fast multiplication of matrix pairs of arbitrary dimension and in many cases improvements are made. Known exponents for fast parallel determination of the solution of linear systems and the related computation of determinant and inverse, are reduced slightly from 2.851 to 2.837. Other applications discussed are sequential algorithms for univariate polynomial factorization over a finite field and a slight improvement to the computational complexity of the linear programming problem with \(m\) constraints and \(n\) variables.