Structured matrices play a relevant role in symbolic and numerical computations. In the literature and in applications we encounter several types of structure, which are typically related to the properties of the problems they stem from: banded structure is often associated with locality of functions or operators, Toeplitz structure arises from shift invariance properties, off-diagonal low-rank structure appears in inverses of banded matrices.

The relationship between univariate polynomial ∈-gcd and factorization of resultant matrices is investigated and several stable and effective algorithms for the computation of an ∈-gcd are proposed. The main result is the design of a practically stable algorithm whose arithmetic cost is quadratic in the degrees of the input polynomials. The algorithm relies on the displacement structure properties of Sylvester and Bezout matrices. Its effectiveness is confirmed by numerical experiments.