Systolic algorithm for polynomial interpolation and related problems

DOI10.1016/S0167-8191(05)80151-6MaRDI QIDQ1179249zbMATH OpenOpenAlexFDO

Authors V. K. Murthy, E. V. Krishnamurthy, Heiko Schröder

Publication date 26 June 1992

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-8191(05)80151-6

zbMATH Keywords

Chinese remainderingevaluation of polynomialsinstruction systolic arrayinterpolationmultivariate interpolationPadé approximantsparallel/distributed algorithmrational interpolationsequential algorithm

Mathematics Subject Classification ID

Interpolation in approximation theory (41A05) Approximation by rational functions (41A20) Padé approximation (41A21) Multidimensional problems (41A63) Numerical interpolation (65D05) Parallel numerical computation (65Y05)

Review text

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.

Recommendations

• Decomposing polynomial interpolation for systolic arrays
• Systolic computation of interpolating polynomials
• Systolic algorithm for rational interpolation and Padé approximation
• Fast parallel algorithm for polynomial interpolation

Cited in

(7)

• Systolic algorithm for rational interpolation and Padé approximation
• Systolic arrays for integer Chinese remaindering
• Fast parallel algorithm for polynomial interpolation
• Systolic computation of interpolating polynomials
• scientific article; zbMATH DE number 4135405 (Why is no real title available?)
• Polynomial multiplication on systolic arrays
• Decomposing polynomial interpolation for systolic arrays

This page was built for publication: Systolic algorithm for polynomial interpolation and related problems

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