Generalized companion matrix for approximate GCD

We study a variant of the univariate approximate 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