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

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

Authors Qiao-Long Huang, Xiao-Shan Gao 

Publication date 15 June 2020

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

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)

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.

Recommendations

• Faster sparse multivariate polynomial interpolation of straight-line programs
• Faster sparse interpolation of straight-line programs
• Interpolation of polynomials given by straight-line programs
• A new deterministic algorithm for sparse multivariate polynomial interpolation
• Sparse polynomial interpolation over fields with large or zero characteristic

Cites work

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

Cited in

(14)

• Randomized interpolation and approximation of sparse polynomials stPreliminary version
• Robust algorithms for sparse interpolation of multivariate polynomials
• Fast multipoint evaluation and interpolation of polynomials in the LCH-basis over F _P ^r
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
• Fast construction of constant bound functions for sparse polynomials
• Sparse polynomial interpolation over fields with large or zero characteristic
• Multivariate sparse interpolation using randomized Kronecker substitutions
• Sparse interpolation over finite fields via low-order roots of unity
• Faster sparse multivariate polynomial interpolation of straight-line programs
• A new deterministic algorithm for sparse multivariate polynomial interpolation
• Faster sparse interpolation of straight-line programs
• On exact division and divisibility testing for sparse polynomials
• Interpolation of polynomials given by 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)