Systolic algorithm for polynomial interpolation and related problems

✍ Scribed by H. Schroder; V.K. Murthy; E.V. Krishnamurthy

• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 362 KB
• Volume: 17
• Category: Article
• ISSN: 0167-8191
• DOI: 10.1016/s0167-8191(05)80151-6

✦ Synopsis

This paper describes a systolic algorithm for interpolation and evaluation of polynomials over any field using a linear array of processors. The periods of these algorithms are O(n) for interpolatin and O(1) for evaluation. This algorithm is readily adapted for Chinese remaindering, easily generahzed for the multivariable interpolation and can be extended for rational interpolation to produce Pade approximants. The instruction systolic array implementation of the algorithm is presented here.