LIFTING/DESCENDING PROCESSES FOR POLYNOMIAL ZEROS

BERNARD MOURRAIN VICTOR PAN

Abstract. The recently proposed Chebyshev-like lifting map for the zeros of a univariate polynomial was motivated by its applications to splitting a univariate polynomial p(x) numerically into factors, which is a major step of some most effective algorithms for approximating polynomial zeros. We complement the Chebyshevlike lifting process by a descending process, decrease the estimated computational cost of performing the algorithm, demonstrate its correlation to Graeffe’s lifting/descending process and generalize lifting from Graeffe’s and Chebyshev-like maps to any fixed rational map of the zeros of the input polynomial.