Asymptotically fast polynomial matrix algorithms for multivariable systems

Claude-Pierre Jeannerod (1) , Gilles Villard (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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).

Mots clés: Linear algebra; Matrix determinant; Matrix inversion; Matrix rank; Matrix reduced form; Nullspace basis; Polynomial matrix

Mots clés: Algèbre linéaire; Base du noyau; Déterminant; Forme réduite; Matrice polynomiale; Rang; Inversion

Domaines: Informatique [cs]

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⟩