Asymptotically fast polynomial matrix algorithms for multivariable systems
Résumé
We present the asymptotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank, nullspace, determinant, generic inverse, reduced form. We show that they essentially can be reduced to two computer algebra techniques, minimal basis computations and matrix fraction expansion/reconstruction, and to polynomial matrix multiplication. Such reductions eventually imply that all these problems can be solved in about the same amount of time as polynomial matrix multiplication (up to logarithmic factors and the size of the output).
Cet article présente les algorithmes actuellement les plus rapides asymptotiquement pour effectuer certaines opérations de base sur les matrices polynomiales : calcul du rang, d’une base du noyau, du déterminant, de l’inverse générique, d’une forme réduite [8, 9, 16, 17]. On montre que ces problèmes se ramènent essentiellement à deux techniques, le calcul de bases minimales et le développement et la reconstruction de fractions de matrices polynomiales, ainsi qu’au produit de matrices polynomiales.Ces réductions impliquent pour ces problèmes l’existence d’algorithmes de résolution dont le coût est de l’ordre de celui du produit de matrices polynomiales (à la taille de la sortie et aux facteurs logarithmiques près).
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...