Systolic computation of interpolating polynomials

DOI10.1007/BF02247877MaRDI QIDQ2641062zbMATH OpenOpenAlexFDO

Authors Peter R. Cappello, E. Gallopoulos, Çetin Kaya Koç

Publication date 1990

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02247877

zbMATH Keywords

Aitken algorithmdivided differencesHermite interpolating polynomialNeville algorithmNewton interpolationsystolic array

Mathematics Subject Classification ID

Interpolation in approximation theory (41A05) Numerical interpolation (65D05) Cellular automata (computational aspects) (68Q80)

Review text

Several time-optimal and spacetime-optimal systolic arrays are presented for computing a process dependence graph corresponding to the Aitken algorithm. It is shown that these arrays also can be used to compute the generalized divided differences, i.e., the coefficients of the Hermite interpolating polynomial. Multivariate generalized divided differences are shown to be efficiently computed on a 2-dimensional systolic array. The techniques also are applied to the Neville algorithm, producing similar results.

Recommendations

• Decomposing polynomial interpolation for systolic arrays
• scientific article; zbMATH DE number 4135405
• Systolic algorithm for polynomial interpolation and related problems
• scientific article; zbMATH DE number 4112025
• Fast computation of divided differences and parallel Hermite interpolation

Cites work

• DERIVATION OF INTERPOLATION FORMULAS IN SEVERAL INDEPENDENT VARIABLES*
• Divided differences for functions of two variables for irregularly spaces arguments
• Efficient Algorithms for Polynomial Interpolation and Numerical Differentiation
• scientific article; zbMATH DE number 3116984 (Why is no real title available?)
• scientific article; zbMATH DE number 3197530 (Why is no real title available?)
• Iterated interpolation using a systolic array
• On Lagrange and Hermite interpolation in R^ k.
• On Multipoint Numerical Interpolation
• On the Analysis and Synthesis of VLSI Algorithms
• Some observations on interpolation in higher dimensions

Cited in

(6)

• Systolic algorithm for polynomial interpolation and related problems
• Polynomial multiplication on systolic arrays
• scientific article; zbMATH DE number 4126707 (Why is no real title available?)
• Decomposing polynomial interpolation for systolic arrays
• Constructing New Time Integrators Using Interpolating Polynomials
• Distributed Computing - IWDC 2004

This page was built for publication: Systolic computation of interpolating polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2641062)