Computing Reviews

Systolic computation of interpolating polynomials
Cappello P., Koç Ç., Gallopoulos E. Computing45(2):95-117,2000.Type:Article
Date Reviewed: 06/01/91

The authors extend work by McKeown on algorithms for interpolation using systolic arrays. They show how slight modifications to McKeown’s array yield three new spacetime-optimal arrays for the construction of the Aitken form of the divided difference table. They then extend this approach to give spacetime-optimal arrays for generalized divided differences, where derivative values as well as function values are used for the table construction. The authors also show how a similar approach can be used to construct arrays for construction of the Neville form of the divided difference table. Finally, they discuss how the results can be extended to functions of two variables. The paper’s conclusion also explains how minor changes in the input allow the arrays to be used for function evaluation. The practical importance of this work comes from the need in certain applications to quickly produce many values of a complicated function. The rapidly falling cost of memory chips could make the combination of a set of function-specific memory chips with a general-purpose interpolation array a cost-effective method for rapid function evaluation.

Reviewer:  A. Genz Review #: CR115016

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy