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.