A new approach to fast polynomial interpolation and multipoint evaluation

DOI10.1016/0898-1221(93)90129-JMaRDI QIDQ1802447zbMATH OpenOpenAlexFDO

Authors Akimou Sadikou, Elliott Landowne, Olen Tiga, Victor Y. Pan

Publication date 21 July 1993

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(93)90129-j

zbMATH Keywords

condition numberfast polynomial interpolationmultipoint polynomial evaluationstabilityToeplitz type linear systems

Mathematics Subject Classification ID

Numerical interpolation (65D05) Computation of special functions and constants, construction of tables (65D20)

Review text

The fastest known algorithms for the problems of multipoint polynomial evaluation are numerically unstable. Therefore the authors use an approach which involves Toeplitz type linear systems for which the stability problems are less serious. The running time depends on the condition number of the auxiliary problem.

Recommendations

• Polynomial evaluation and interpolation and transformations of matrix structures
• scientific article; zbMATH DE number 1405666
• scientific article; zbMATH DE number 1083142
• Polynomial evaluation and interpolation on special sets of points
• Fast evaluation and interpolation at the Chebyshev sets of points

Cites work

• A fast algorithm for the discrete Laplace transformation
• Asymptotically fast solution of Toeplitz and related systems of linear equations
• Evaluating Polynomials at Fixed Sets of Points
• Fast Parallel Algorithms for QR and Triangular Factorization
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 1263320 (Why is no real title available?)
• On Computations with Dense Structured Matrices
• Rapid solution of integral equations of classical potential theory
• Stability of Methods for Solving Toeplitz Systems of Equations
• Superfast Solution of Real Positive Definite Toeplitz Systems

Cited in

(18)

• An efficient raster evaluation method for univariate polynomials
• Structured matrices and Newton's iteration: unified approach
• Parallel computation of polynomial GCD and some related parallel computations over abstract fields
• New transformations of Cauchy matrices and Trummer's problem
• An efficient solution for Cauchy-like systems of linear equations
• An algebraic approach to approximate evaluation of a polynomial on a set of real points
• Efficient Ehrlich-Aberth iteration for finding intersections of interpolating polynomials and rational functions
• Semialgebraic sets and real binary forms decompositions
• scientific article; zbMATH DE number 5714299 (Why is no real title available?)
• scientific article; zbMATH DE number 1254017 (Why is no real title available?)
• scientific article; zbMATH DE number 1083142 (Why is no real title available?)
• A Note on Polynomial Interpolation
• Transformations of matrix structures work again
• Fast multipoint evaluation and interpolation of polynomials in the LCH-basis over F _P ^r
• Polynomial evaluation and interpolation and transformations of matrix structures
• Fast approximate computations with Cauchy matrices and polynomials
• Fast evaluation of polynomials by rational preparation
• scientific article; zbMATH DE number 7709336 (Why is no real title available?)

This page was built for publication: A new approach to fast polynomial interpolation and multipoint evaluation

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