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 :
Reports
Complete list of metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101878
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:50 AM
Last modification on : Friday, May 17, 2019 - 1:39:22 AM

File

RR2003-02.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101878, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

8

Files downloads

30