Computing the rank and a small nullspace basis of a polynomial matrix - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2005

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

Résumé

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.
Nous réduisons le problème du calcul du rang et du noyau d’une matrice polynomiale d’une variable, à la multiplication de deux matrices polynomiales. Pour une matrice nxn de degré d en entrée sur un corps K, nous donnons un algorithme de calcul du rang et du noyau dont le coût est grosso modo celui du produit de deux matrices de dimension n et de degré d. Si cette multiplication s’effectue en MM(n,d)=softO((n^omega d) opérations, où oméga l’exposant du produit de matrices sur K, alors l’algorithme nécessite O ̃(MM(n, d)) opérations dans K. Pour une matrice mxn de rang r et degré d, l’expression générale est O ̃(nmrω−2d). La notation «soft-O» indique des facteurs logarithmiques éludés. La méthode est probabiliste certifiée sur le mode Las Vegas. Nous obtenons ces résultats en combinant une remontée de Hensel aux grands ordres avec une reconstruction de fraction matricielle, ainsi que grâce à un calcul de bases minimales (ou presque) dans le noyau vu comme K[x]-module.
Fichier principal
Vignette du fichier
RR2005-03.pdf (410.43 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101902 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101902 , version 1

Citer

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⟩
18 Consultations
193 Téléchargements

Partager

Gmail Facebook X LinkedIn More