On the complexities of multipoint evaluation and interpolation

DOI10.1016/J.TCS.2004.09.002zbMATH Open1086.68150OpenAlexW2129389061MaRDI QIDQ706626FDOQ706626

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

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

zbMATH Keywords

InterpolationComplexityPolynomial evaluation

Mathematics Subject Classification ID

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

Cites Work

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

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)