Affordable Access

Publisher Website

Sylvester–Habicht Sequences and Fast Cauchy Index Computation

Journal of Symbolic Computation
Publication Date
DOI: 10.1006/jsco.2000.0427
  • Computer Science


Abstract 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 complexity O ( 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 is O( d 2 τ· 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.

There are no comments yet on this publication. Be the first to share your thoughts.