Portal de Periódicos da CAPES

Evaluating Polynomials at Fixed Sets of Points

1975; Society for Industrial and Applied Mathematics; Volume: 4; Issue: 4 Linguagem: Inglês

10.1137/0204045

1095-7111

Alfred V. Aho, K. Steiglitz, Jeffrey D. Ullman,

Polynomial and algebraic computation

We investigate the evaluation of an $(n - 1)$st degree polynomial at a sequence of n points. It is shown that such an evaluation reduces directly to a simple convolution if and only if the sequence of points is of the form $b, ba,ba^2 , \cdots ,ba^{n - 1} $ for complex numbers a and b (the so-called "chirp transform"). By more complex reductions we develop an $O(n\log n)$ evaluation algorithm for sequences of points of the form \[ b + c + d,\quad ba^2 + ca + d,\quad ba^4 + ca^2 + d, \cdots \] for complex numbers a, b, c and d. Finally we show that the evaluation of an $(n - 1)$st-degree polynomial and all its derivatives at a single point requires at most $O(n\log n)$ steps.