Decomposing polynomial interpolation for systolic arrays

Abstract

This paper (1) summarizes recent work on systolic computation of interpolating polynomials, presenting several time-optimal and spacetime-optimal systolic arrays for computing a process dependence graph for Aitken's algorithm, and (2) presents an efficient decomposition of the computation by partitioning the corresponding so-called Newton-Vandermonde matrix. Such a decomposition is used to treat an interpolation problem whose size exceeds the array size.

Keywords:

• Newton and Hermite interpolation
• Aitken's algorithm
• systolic array
• extent problem
• decomposition
• Newton-Vandermonde matrix