Accelerated Approximation of the Complex Roots of a Univariate Polynomial (Extended Abstract)

Victor Y. Pan (1) , Elias Tsigaridas (2)

1 Department of Mathematics and Computer Science [Lehman]
2 PolSys - Polynomial Systems

Highly efficient and even nearly optimal algorithms have been developed for the classical problem of univariate polynomial root-finding (see, e.g., \cite{P95}, \cite{P02}, \cite{MNP13}, and the bibliography therein), but this is still an area of active research. By combining some powerful techniques developed in this area we devise new nearly optimal algorithms, whose substantial merit is their simplicity, important for the implementation.

Mots clés: polynomials; fast polynomial division; Boolean comlexity; approximate computations; rational functions; multipoint evaluation; interpolation; precision of computing

Domaines: Calcul formel [cs.SC]

Victor Y. Pan, Elias Tsigaridas. Accelerated Approximation of the Complex Roots of a Univariate Polynomial (Extended Abstract). SNC '14 - Symposium on Symbolic-Numeric Computation, Jul 2014, Shanghai, China. pp.132-134, ⟨10.1145/2631948.2631973⟩. ⟨hal-00980584⟩