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

AbstractAn algorithm for the computation of the LU factorization over the integers of an n × n Bezoutian B is presented. The algorithm requires O(n2) 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(n2) 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 [2] and on the properties of the Schur complements of Bezoutians [4], improve the ones of [28,8,1]