FFT-based Computation of Polynomial Coefficients and Related Tasks

2016/07/12 by Hans-Rudolf Thomann, Thomann, Hans-Rudolf
Computer Science · #Digital Filter Design and Implementation #FOS: Mathematics #Numerical Analysis (math.NA) #Numerical Methods and Algorithms #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1608.01357

openalex publication_date 2016/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a FFT-based algorithm for the computation of a polynomial's coefficients from its roots, and apply it to obtain the coefficients of interpolation polynomials, to invert Vandermondians and to evaluate the symmetric functions of a set of parameters. Analytic and numerical evidence with problem sizes up to and beyond n=2000 confirms that it is superior over previous algorithms for these problems in case of parameters taken from uniform or almost uniform distributions on or near circles in the complex plane, and of comparable performance in other cases. Its time complexity is O(n*n) and its storage complexity for tasks other than Vandermondian inversion O(n).

Related

• Fast polynomial transforms based on Toeplitz and Hankel matrices
• Neville's algorithm revisited
• A Quadratic-Time Algorithm for General Multivariate Polynomial Interpolation
• An in-place truncated Fourier transform and applications to polynomial multiplication
• Fast evaluation and root finding for polynomials with floating-point coefficients