Sparse polynomial interpolation based on derivatives

DOI10.1016/j.jsc.2022.06.002OpenAlexW4283383949MaRDI QIDQ2156377

Qiao-Long Huang

Publication date: 18 July 2022

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2002.03708

zbMATH Keywords

derivativessparse polynomialsstraight-line program

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Numerical approximation and computational geometry (primarily algorithms) (65Dxx) Computational number theory (11Yxx)

Cites Work

• Unnamed Item
• Interpolating polynomials from their values
• Deterministically testing sparse polynomial identities of unbounded degree
• Interpolation of polynomials given by straight-line programs
• The complexity of partial derivatives
• Revisit sparse polynomial interpolation based on randomized Kronecker substitution
• Newton-Hensel interpolation lifting
• Faster sparse multivariate polynomial interpolation of straight-line programs
• Output-Sensitive Algorithms for Sumset and Sparse Polynomial Multiplication
• Modern Computer Algebra
• Sparse interpolation over finite fields via low-order roots of unity
• Evaluating Derivatives
• Greatest common divisors of polynomials given by straight-line programs
• Randomized Interpolation and Approximation of Sparse Polynomials
• Sparse Polynomial Interpolation over Fields with Large or Zero Characteristic
• Faster Sparse Interpolation of Straight-Line Programs
• Diversification improves interpolation
• Fast construction of irreducible polynomials over finite fields