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 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.
Extended companion matrix for approximate GCD
Boito, P.;
2011-01-01
Abstract
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 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
