HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Accelerated Approximation of the Complex Roots and Factors of a Univariate Polynomial

Victor Y. Pan 1 Elias Tsigaridas 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : The known algorithms approximate the roots of a complex univariate polynomial in nearly optimal arithmetic and Boolean time. They are, however, quite involved and require a high precision of computing when the degree of the input polynomial is large, which causes numerical stability problems. We observe that these difficulties do not appear at the initial stages of the algorithms, and in our present paper we extend one of these stages, analyze it, and avoid the cited problems, still achieving the solution within a nearly optimal complexity estimates, provided that some mild initial isolation of the roots of the input polynomial has been ensured. The resulting algorithms promise to be of some practical value for root-finding and can be extended to the problem of polynomial factorization, which is of interest on its own right. We conclude with outlining such an extension, which enables us to cover the cases of isolated multiple roots and root clusters.
Document type :
Journal articles
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

Contributor : Elias Tsigaridas Connect in order to contact the contributor
Submitted on : Saturday, December 12, 2015 - 3:38:51 PM
Last modification on : Thursday, February 3, 2022 - 11:15:38 AM
Long-term archiving on: : Saturday, April 29, 2017 - 12:09:00 PM


Files produced by the author(s)



Victor Y. Pan, Elias Tsigaridas. Accelerated Approximation of the Complex Roots and Factors of a Univariate Polynomial. Theoretical Computer Science, Elsevier, 2017, 681, ⟨10.1016/j.tcs.2017.03.030⟩. ⟨hal-01105267v2⟩



Record views


Files downloads