MANIPULATING POLYNOMIALS IN GENERALIZED FORM

We present new algorithms using structured matrix methods for manipulating polynomials expressed in generalized form, that is, relative to a polynomial basis $\{p_i(x)\}$ satisfying a three-term recurrence relation. This includes computing the Euclidean remainders as well as the greatest common divisor of two polynomials $u(x)$ and $v(x)$ of degrees less than $n$. The computational schemes involve solving linear systems with nested Hankel matrices represented in the given generalized basis and they reach the optimal sequential complexity of $O(n^2)$ arithmetical operations.