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

DOI10.1016/J.JSC.2019.10.005MaRDI QIDQ2188992zbMATH OpenOpenAlexWikidataFDO

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

black boxinterpolationKronecker substitution

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

• -discrepancy sets and their application for interpolation of sparse polynomials
• 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

Cited in

(17)

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

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)