C. Brunie & P. Saux-Picart


Titre: "A fast version of the Schur-Cohn algorithm"


Résumé: In this paper we describe a fast algorithm for counting the number of roots of complex polynomials in the open unit disk, classically called the \textsc{Schur-Cohn} problem. It uses FFT and dichotomic process. For degree $d$ polynomials our bound is of order $d \log^2 d$ in terms of field operations and comparisons, but our approach nicely allows to integrate the bit size as a further complexity parameter as well. For bit size $\sigma$ of input polynomials of $\Z[X]$ our running time is of order $d^2\sigma \cdot \log(d\sigma) \cdot \log \log(d\sigma) \cdot \log(d)$ in the multi-tape Turing machine model, thus improving all previously proposed approaches.

---

Sommaire