Systolic algorithm for polynomial interpolation and related problems (Q1179249)

The aim of this paper is to describe a systolic algorithm for interpolation and evaluation of polynomials over any field using a linear array of processors. A sequential algorithm and a parallel/distributed algorithm for Chinese remaindering/interpolation problem are both presented and discussed. Listings of programs and examples are presented, too. The periods of these algorithms are \(O(n)\) for interpolation and \(O(1)\) for evaluation. The authors present an instruction systolic array implementation of the algorithm. The algorithm is adapted for Chinese remaindering, but it is easily generalized for multivariate interpolation and can be extended for rational interpolation to produce Padé approximants.