Skip to Main content Skip to Navigation

On the Complexity of Polynomial Matrix Computations

Abstract : 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.
Document type :
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:50 AM
Last modification on : Wednesday, November 20, 2019 - 3:14:33 AM


Files produced by the author(s)


  • HAL Id : hal-02101878, version 1



Pascal Giorgi, Claude-Pierre Jeannerod, Gilles Villard. On the Complexity of Polynomial Matrix Computations. [Research Report] LIP RR-2003-2, Laboratoire de l'informatique du parallélisme. 2003, 2+15p. ⟨hal-02101878⟩



Record views


Files downloads