Multivariate sparse interpolation using randomized Kronecker substitutions

DOI10.1145/2608628.2608674MaRDI QIDQ3452374zbMATH OpenOpenAlexFDO

Authors Andrew Arnold, Daniel S. Roche

Publication date 11 November 2015

Published in Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

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

zbMATH Keywords

Kronecker substitutionmultivariate polynomialsrandomized algorithmssparse interpolation

Mathematics Subject Classification ID

Interpolation in approximation theory (41A05) Numerical interpolation (65D05) Randomized algorithms (68W20) Symbolic computation and algebraic computation (68W30)

Abstract: We present new techniques for reducing a multivariate sparse polynomial to a univariate polynomial. The reduction works similarly to the classical and widely-used Kronecker substitution, except that we choose the degrees randomly based on the number of nonzero terms in the multivariate polynomial, that is, its sparsity. The resulting univariate polynomial often has a significantly lower degree than the Kronecker substitution polynomial, at the expense of a small number of term collisions. As an application, we give a new algorithm for multivariate interpolation which uses these new techniques along with any existing univariate interpolation algorithm.

Recommendations

• Revisit sparse polynomial interpolation based on randomized Kronecker substitution
• Deterministic sparse interpolation of black-box multivariate polynomials using Kronecker type substitutions
• Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications
• Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs
• Sparse polynomial interpolation with finitely many values for the coefficients

Cites work

• An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
• Cylindrical algebraic decomposition using validated numerics
• Definability and decision problems in arithmetic
• scientific article; zbMATH DE number 1952952 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• On Computable Numbers, with an Application to the Entscheidungsproblem
• The Jordan Curve Theorem, Formally and Informally

Cited in

(11)

• Sparse interpolation in terms of multivariate Chebyshev polynomials
• Sparse polynomial interpolation based on diversification
• Revisit sparse polynomial interpolation based on randomized Kronecker substitution
• Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs
• Faster sparse multivariate polynomial interpolation of straight-line programs
• Deterministic sparse interpolation of black-box multivariate polynomials using Kronecker type substitutions
• Fast interpolation of multivariate polynomials with sparse exponents
• Sparse polynomial interpolation: faster strategies over finite fields
• Fast interpolation and multiplication of unbalanced polynomials
• A new sparse polynomial GCD by separating terms
• Practical cryptanalysis of pseudorandom correlation generators based on quasi-abelian syndrome decoding

Describes a project that uses

Uses Software

• Jordan

This page was built for publication: Multivariate sparse interpolation using randomized Kronecker substitutions

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