Deterministic sparse interpolation of black-box multivariate polynomials using Kronecker type substitutions

DOI10.1360/N012019-00018MaRDI QIDQ5064243zbMATHFDO

Authors Qiao-Long Huang, Xiao-Shan Gao

Publication date 21 March 2022

Published in SCIENTIA SINICA Mathematica (Search for Journal in Brave)

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

zbMATH Keywords

sparse polynomial interpolationKronecker substitutionblack-box model

Mathematics Subject Classification ID

Numerical interpolation (65D05) Interpolation in approximation theory (41A05) Algorithms for approximation of functions (65D15)

Abstract: In this paper, we propose two new deterministic interpolation algorithms for a sparse multivariate polynomial given as a standard black-box by introducing new Kronecker type substitutions. Let $finRB[x_1,dots,x_n]$ be a sparse black-box polynomial with a degree bound $D$. When $RB=C$ or a finite field, our algorithms either have better bit complexity or better bit complexity in $D$ than existing deterministic algorithms. In particular, in the case of deterministic algorithms for standard black-box models, our second algorithm has the current best complexity in $D$ which is the dominant factor in the complexity.

Recommendations

• Revisit sparse polynomial interpolation based on randomized Kronecker substitution
• A new deterministic algorithm for sparse multivariate polynomial interpolation
• Sparse polynomial interpolation with finitely many values for the coefficients
• Multivariate sparse interpolation using randomized Kronecker substitutions
• A new algorithm for sparse interpolation of multivariate polynomials

Cited in

(3)

• Revisit sparse polynomial interpolation based on randomized Kronecker substitution
• Multivariate sparse interpolation using randomized Kronecker substitutions
• A new deterministic algorithm for sparse multivariate polynomial interpolation

This page was built for publication: Deterministic sparse interpolation of black-box multivariate polynomials using Kronecker type substitutions

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