Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs

DOI10.1016/J.JSC.2019.10.005zbMATH Open1445.65005arXiv1709.08979OpenAlexW2980587714WikidataQ127010561 ScholiaQ127010561MaRDI QIDQ2188992FDOQ2188992

Qiao-Long Huang, Xiao-Shan Gao

Publication date: 15 June 2020

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

Abstract: In this paper, we propose new deterministic and Monte Carlo interpolation algorithms for sparse multivariate polynomials represented by straight-line programs. Let $f$ be an $n$-variate polynomial given by a straight-line program, which has a degree bound $D$ and a term bound $T$. Our deterministic algorithm is quadratic in $n,T$ and cubic in $logD$ in the Soft-Oh sense, which has better complexities than existing deterministic interpolation algorithms in most cases. Our Monte Carlo interpolation algorithms have better complexities than existing Monte Carlo interpolation algorithms and are the first algorithms whose complexities are linear in $nT$ in the Soft-Oh sense. Since $nT$ is a factor of the size of $f$, our Monte Carlo algorithms are optimal in $n$ and $T$ in the Soft-Oh sense.

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

zbMATH Keywords

interpolationKronecker substitutionblack box

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical interpolation (65D05)

Cites Work

• Randomized Interpolation and Approximation of Sparse Polynomials
• Interpolating polynomials from their values
• Modern computer algebra
• Interpolation of polynomials given by straight-line programs
• Randomness efficient identity testing of multivariate polynomials
• \(\varepsilon\)-discrepancy sets and their application for interpolation of sparse polynomials
• Newton-Hensel interpolation lifting
• Faster sparse multivariate polynomial interpolation of straight-line programs
• Sparse interpolation over finite fields via low-order roots of unity
• Diversification improves interpolation
• Multivariate sparse interpolation using randomized Kronecker substitutions
• Faster Sparse Interpolation of Straight-Line Programs

Cited In (6)

• Randomized interpolation and approximation of sparse polynomials stPreliminary version
• Fast multipoint evaluation and interpolation of polynomials in the LCH-basis over F _P ^r
• Fast construction of constant bound functions for sparse polynomials
• On exact division and divisibility testing for sparse polynomials
• Robust algorithms for sparse interpolation of multivariate polynomials
• Faster sparse multivariate polynomial interpolation of straight-line programs

This page was built for publication: Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs

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