Amortized Bound for Root Isolation via Sturm Sequences
Zilin Du, Vikram Sharma, Chee Keng Yap · Birkhäuser Basel eBooks · 2007
This paper presents two results on the complexity of root isolation via Sturm sequences. Both results exploit amortization arguments.For a square-free polynomial A (X) of degree d with L-bit integer coefficients, we use an amortization argument to show that all the roots, real or complex, can be isolated using at most O(dL + dlgd) Sturm probes. This extends Davenport’s result for the case of isolating all real roots.We also show that a relatively straightforward algorithm, based on the classical subresultant PQS, allows us to evaluate the Sturm sequence of A(X) at rational Õ(dL)-bit values in time Õ(d 3 L); here the Õ-notation means we ignore logarithmic factors. Again, an amortization argument is used. We provide a family of examples to show that such amortization is necessary.