On the complexities of multipoint evaluation and interpolation

DOI10.1016/j.tcs.2004.09.002zbMath1086.68150OpenAlexW2129389061MaRDI QIDQ706626

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

ComplexityInterpolationPolynomial evaluation

Mathematics Subject Classification ID

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

Related Items (1)

Fast arithmetic for triangular sets: from theory to practice

Cites Work

• Interpolating polynomials from their values
• On fast multiplication of polynomials over arbitrary algebras
• Fast modular transforms
• Complexity of multiplication with vectors for structured matrices
• Fast algorithms with preprocessing for matrix-vector multiplication problems
• Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey
• An inversion formula and fast algorithms for Cauchy-Vandermonde matrices
• Polynomial evaluation and interpolation on special sets of points
• Fast multiplication of large numbers
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Inter-reciprocity applied to electrical networks
• Evaluating Polynomials at Fixed Sets of Points
• Computing Elementary Symmetric Polynomials with a Subpolynomial Numberof Multiplications
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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