Skip to Main content Skip to Navigation

Computing the rank and a small nullspace basis of a polynomial matrix

Abstract : We reduce the problem of computing the rank and a nullspace basis of a univariate polynomial matrix to polynomial matrix multiplication. For an input n x n matrix of degree d over a field K we give a rank and nullspace algorithm using about the same number of operations as for multiplying two matrices of dimension n and degree d. If the latter multiplication is done in MM(n,d)=softO((n^omega)d) operations, with omega the exponent of matrix multiplication over K, then the algorithm uses softO(MM(n,d)) operations in K. For m x n matrices of rank r and degree d, the cost expression is softO(nmr^(omega -2)d). The softO notation indicates some missing logarithmic factors. The method is randomized with Las Vegas certification. We achieve our results in part through a combination of matrix Hensel high-order lifting and matrix minimal fraction reconstruction, and through the computation of minimal or small degree vectors in the nullspace seen as a K[x]-module.
Document type :
Complete list of metadata

Cited literature [40 references]  Display  Hide  Download
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:09:22 AM
Last modification on : Saturday, September 11, 2021 - 3:19:17 AM


Files produced by the author(s)


  • HAL Id : hal-02101902, version 1



Arne Storjohann, Gilles Villard. Computing the rank and a small nullspace basis of a polynomial matrix. [Research Report] LIP RR-2005-3, Laboratoire de l'informatique du parallélisme. 2005, 2+24p. ⟨hal-02101902⟩



Les métriques sont temporairement indisponibles