A Fast Schur–Euclid-Type Algorithm for Quasiseparable Polynomials

In this paper, a fast O(n2) algorithm is presented for computing recursive triangular factorization of a Bezoutian matrix associated with quasiseparable polynomials via a displacement equation. The new algorithm applies to a fairly general class of quasiseparable polynomials that includes real orthogonal, Szegö polynomials, and several other important classes of polynomials, e.g., those defined by banded Hessenberg matrices. While the algorithm can be seen as a Schur-type for the Bezoutian matrix it can also be seen as a Euclid-type for quasiseparable polynomials via factorization of a displacement equation. The process, i.e., fast Euclid-type algorithm for quasiseparable polynomials or Schur-type algorithm for Bezoutian associated with quasiseparable polynomials, is carried out with the help of a displacement equation satisfied by Bezoutian and Confederate matrices leading to O(n2) complexity.