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.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...