# Fast fraction-free triangularization of Bezoutians with applications to sub-resultant chain computation

An algorithm for the computation of the LU factorization over the
integers of an $n\times n$ Bezoutian $B$ is presented.
The algorithm requires $O(n^2)$ arithmetic operations and involves
integers having at most $O(n\log nc)$ bits, where $c$ is an upper
bound of the moduli
of the integer entries of $B$. As an application, by using the
correlations between Bezoutians and the Euclidean scheme, we devise a
new division-free algorithm for the computation of the polynomial
pseudo-remainder sequence of two polynomials of degree at most $n$ in
$O(n^2)$ arithmetic operations. The growth of the length of the
integers involved in the computation is kept at the minimum value,
i.e., $O(n\log nc)$ bits, no matter if the sequence is normal or not,
where $c$ is an upper bound of the moduli of the
input coefficients.
The algorithms, that rely on the Bareiss technique and on the
properties of the Schur complements of Bezoutians ,
improve the previous ones.