On the Complexity of Polynomial Matrix Computations

(eng) We study the link between the complexity of polynomial matrix multiplication and the complexity of solving other basic linear algebra problems on polynomial matrices. By polynomial matrices we mean n x n matrices of degree d over K[x] where K is a commutative field. Under the straight-line program model we show that multiplication is reducible to the problem of computing the coefficient of degree d of the determinant. Conversely, we propose algorithms for minimal approximant computation and column reduction that are based on polynomial matrix multiplication; for the determinant, the straight-line program we give also relies on matrix product over K[x] and provides an alternative to Storjohann's determinant algorithm. We further show that all these problems can be solved in particular in O~(n^w d) operations in K. Here the "soft Oh'' notation O~ indicates some missing log(nd) factors and w is the exponent of matrix multiplication overK