  We consider the computation of roots of polynomials expressed in the
Chebyshev basis. We extend the QR iteration presented in [Eidelman, Y.,
Gemignani, L., and Gohberg, I., Numer. Algorithms, 47.3 (2008): pp. 253-273]
introducing an aggressive early deflation strategy, and showing that the
rank-structure allows to parallelize the algorithm avoiding data dependencies
which would be present in the unstructured QR. We exploit the particular
structure of the colleague linearization to achieve quadratic complexity and
linear storage requirements. The (unbalanced) QR iteration used for Chebyshev
rootfinding does not guarantee backward stability on the polynomial
coefficients, unless the vector of coefficients satisfy $\|p\| \approx 1$, an
hypothesis which is almost never verified for polynomials approximating smooth
functions. Even though the presented method is mathematically equivalent to the
unbalanced QR algorithm, we show that exploiting the rank structure allows to
guarantee a small backward error on the polynomial, up to an explicitly
computable amplification factor $\hat\gamma_1(p)$, which depends on the
polynomial under consideration. We show that this parameter is almost always of
moderate size, making the method accurate on several numerical tests, in
contrast with what happens in the unstructured unbalanced QR.
