A New Algorithm for Multipoint Evaluation of Univariate Polynomials

Abstract

Let l i n l lin x axp    1 0)( be a univariate polynon mial of degree 1 n defined on ] [x ,where ][ x denotes the ring of polynomials in x over  , the field of real numbers and let } ,,{ 1 0  nxxS  be any set of mdistinct elements in .  The role of Multipoint Evaluation Problem (MEP) is to compute the finite sum l i n l lin x axp    1 0)( for all . ,,, mi 10 These types of evaluations are used most abundantly in many areas such as Engineering, Physics, Medicine, and Weather forecasting. The MEP of interest in this paper is restricted to the case where n m .The paper proposes a new algorithm with asymptotic time complexity of ) ( 2 nO for the MEP. For the sake of simplicity, we assume that ,kn 2 where  ,,, 210k .We explore performance of the algorithm by means of numerical experiments. The numerical results confirm that the algorithm is faster than Estrin’s method and that it is as accurate as Estrin’s method.