Sylvester–Habicht Sequences and Fast Cauchy Index Computation

In this paper we show how Schönhage’s strategy for computing continued fractions (Schönhage 1971) can be combined with the theory of sub-resultants (Habicht, 1948; Collins, 1967; Brown, 1971; Brown and Traub, 1971; Loos, 1982; Gonzalez et al., 1990, 1994; Ducos, 1996; Ho and Yap, 1996; Lazard, 1998; Quitté, 1998) in order to compute the Cauchy index of a rational function or the signature of a non-singular Hankel matrix in a fast and also storage efficient way. Over the integers our algorithms have bit complexityO (M(d, σ) •log(d)) withσ = O(dτ) where M(d,σ ) = O(dσ•log(dσ) •loglog(dσ)) is Schönhage’s bound for multiplication of integer polynomials of degrees bounded by d and bit size bounded by σ in the multi-tape Turing machine model (Schönhage, 1982). Thus our bound isO(d2τ•log(dτ) •loglog(dτ) •log(d)).As a byproduct of the necessary analysis we obtain a refinement of the Sub-resultant Theorem. We present a new exact divisibility for sub-resultants in the defective case which extends the formulæ for the non-defective situation in a natural way. We also prove that the size of coefficients in the ordinary remainder sequence is quadratic in d.