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

Cited literature [20 references]  Display  Hide  Download

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

File

RR2005-03.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101902, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

7

Files downloads

30