Asymptotically fast polynomial matrix algorithms for multivariable systems - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 2005

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).
Fichier principal
Vignette du fichier
RR2005-36.pdf (280.9 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02102206 , version 1

Citer

Claude-Pierre Jeannerod, Gilles Villard. Asymptotically fast polynomial matrix algorithms for multivariable systems. [Research Report] LIP RR-2005-36, Laboratoire de l'informatique du parallélisme. 2005, 2+12p. ⟨hal-02102206⟩
20 Consultations
109 Téléchargements

Partager

More