The complexity of evaluating interpolation polynomials

DOI10.1016/0304-3975(85)90078-7MaRDI QIDQ1081273zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1985

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(85)90078-7

zbMATH Keywords

coefficients of the Lagrangian interpolation polynomialcomplexity bounds

Mathematics Subject Classification ID

Interpolation in approximation theory (41A05) Numerical interpolation (65D05) Analysis of algorithms and problem complexity (68Q25)

Review text

It is well known that the complexity of computing all coefficients of the Lagrangian interpolation polynomial for n nodes and n values is of order n log n. Proving in this paper a more general theorem with respect to the complexity bounds of the tasks of computing the coefficients of the Lagrangian interpolation polynomials, the author derives from this the previous result about the complexity order n log n.

Recommendations

• Polynomial evaluation and interpolation on special sets of points
• Interpolation of polynomials given by straight-line programs
• Lower complexity bounds for interpolation algorithms
• On the complexities of multipoint evaluation and interpolation
• scientific article; zbMATH DE number 69493

Cites work

• A fast method for interpolation using preconditioning
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• scientific article; zbMATH DE number 3873251 (Why is no real title available?)
• scientific article; zbMATH DE number 3545079 (Why is no real title available?)
• scientific article; zbMATH DE number 3628385 (Why is no real title available?)
• scientific article; zbMATH DE number 3349977 (Why is no real title available?)
• The complexity of partial derivatives

Cited in

(15)

• Lagrange interpolation on a processor tree with ring connections
• Semi-algebraic decision complexity, the real spectrum, and degree
• Lower complexity bounds for interpolation algorithms
• MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity
• scientific article; zbMATH DE number 421669 (Why is no real title available?)
• Arithmetic complexity of the Stirling transforms
• Complexity of interpolation and related problems in positive calculi
• scientific article; zbMATH DE number 917814 (Why is no real title available?)
• On the Complexity of the Interlace Polynomial
• Combinatorial algorithms for the interpolation of polynomials in dimension 2
• Quantum cryptanalysis of Farfalle and (generalised) key-alternating Feistel networks
• Fast evaluation of interlace polynomials on graphs of bounded treewidth
• Weighted Ehrhart functions
• On the complexities of multipoint evaluation and interpolation
• Interpolation cryptanalysis of unbalanced Feistel networks with low degree round functions

This page was built for publication: The complexity of evaluating interpolation polynomials

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