Matrice compagnon généralisée et calcul du pgcd approché

par Paola Boito (Université de Limoges ; CNRS ; XLIM DMI)

jeudi 31 mars 2011, 10:30 → 11:30 Europe/Paris

XR.203 (Bâtiment XLIM)

We study a variant of the univariate approximate polynomial GCD problem, where the coefficients of one polynomial $f(x)$ are known exactly, whereas the coefficients of the second polynomial $g(x)$ may be perturbed. Our approach relies on the properties of the matrix which describes the operator of multiplication by $g$ in the quotient ring $\mathbb{C}[x]/(f)$. In particular, the structure of the null space of the multiplication matrix contains all the essential information about GCD(f,g). Moreover, the multiplication matrix exhibits a displacement structure that allows us to design a fast algorithm for approximate GCD computation with quadratic complexity w.r.t. polynomial degrees.