On the complexities of multipoint evaluation and interpolation

DOI10.1016/J.TCS.2004.09.002MaRDI QIDQ706626zbMATH OpenOpenAlexFDO

Authors Alin Bostan, Éric Schost

Publication date 9 February 2005

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

Full work available at URL https://doi.org/10.1016/j.tcs.2004.09.002

zbMATH Keywords

InterpolationComplexityPolynomial evaluation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Polynomial evaluation and interpolation on special sets of points
• The complexity of evaluating interpolation polynomials
• Multi-point evaluation in higher dimensions
• Polynomial evaluation and interpolation and transformations of matrix structures
• Lower bounds for polynomial evaluation and interpolation problems

Cites work

• scientific article; zbMATH DE number 1682655 (Why is no real title available?)
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 3533996 (Why is no real title available?)
• scientific article; zbMATH DE number 3539809 (Why is no real title available?)
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 2151179 (Why is no real title available?)
• scientific article; zbMATH DE number 3078328 (Why is no real title available?)
• An inversion formula and fast algorithms for Cauchy-Vandermonde matrices
• Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey
• Complexity of multiplication with vectors for structured matrices
• Computing Elementary Symmetric Polynomials with a Subpolynomial Numberof Multiplications
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Evaluating Polynomials at Fixed Sets of Points
• Fast algorithms with preprocessing for matrix-vector multiplication problems
• Fast modular transforms
• Fast multiplication of large numbers
• Inter-reciprocity applied to electrical networks
• Interpolating polynomials from their values
• Modern computer algebra
• On fast multiplication of polynomials over arbitrary algebras
• Polynomial evaluation and interpolation on special sets of points

Cited in

(4)

• Multi-point evaluation in higher dimensions
• Polynomial evaluation and interpolation on special sets of points
• The complexity of evaluating interpolation polynomials
• Fast arithmetic for triangular sets: from theory to practice

This page was built for publication: On the complexities of multipoint evaluation and interpolation

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