Early termination in sparse interpolation algorithms

DOI10.1016/S0747-7171(03)00088-9zbMath1074.68080OpenAlexW2126318803MaRDI QIDQ1878478

Wen-Shin Lee, Erich L. Kaltofen

Publication date: 20 August 2004

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

Full work available at URL: https://doi.org/10.1016/s0747-7171(03)00088-9

zbMATH Keywords

InterpolationRandomized algorithmSparse polynomialBlack box polynomialEarly terminationSparse interpolation

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Polynomials, factorization in commutative rings (13P05)

Related Items (32)

Numerical reconstruction of convex polytopes from directional moments ⋮ Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases ⋮ An improved early termination sparse interpolation algorithm for multivariate polynomials ⋮ A new algorithm for sparse interpolation of multivariate polynomials ⋮ Validated analysis of modulated signals: from de Prony to Padé and beyond ⋮ Reconstruction of sparse Legendre and Gegenbauer expansions ⋮ Multivariate exponential analysis from the minimal number of samples ⋮ Learning algebraic decompositions using Prony structures ⋮ Sparse polynomial interpolation with Bernstein polynomials ⋮ Resultant elimination via implicit equation interpolation ⋮ On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field ⋮ Multiscale matrix pencils for separable reconstruction problems ⋮ Integral reduction with Kira 2.0 and finite field methods ⋮ Interpolation of dense and sparse rational functions and other improvements in \texttt{FireFly} ⋮ On the evaluation of some sparse polynomials ⋮ Sparse interpolation of multivariate rational functions ⋮ A fraction free matrix Berlekamp/Massey algorithm ⋮ Sparse polynomial interpolation in Chebyshev bases ⋮ Reconstructing rational functions with \texttt{FireFly} ⋮ Detecting lacunary perfect powers and computing their roots ⋮ Reconstruction of stationary and non-stationary signals by the generalized Prony method ⋮ On computing the degree of a Chebyshev polynomial from its value ⋮ Foreword ⋮ A fast parallel sparse polynomial GCD algorithm ⋮ Symbolic-numeric sparse interpolation of multivariate polynomials ⋮ Tropical algebraic geometry in Maple: a preprocessing algorithm for finding common factors for multivariate polynomials with approximate coefficients ⋮ Chunky and equal-spaced polynomial multiplication ⋮ How to get high resolution results from sparse and coarsely sampled data ⋮ Prony methods for recovery of structured functions ⋮ Interpolation of polynomials given by straight-line programs ⋮ Sparse interpolation in terms of multivariate Chebyshev polynomials ⋮ Accurate solution of near-colliding Prony systems via decimation and homotopy continuation

Uses Software

• Dagwood
• FOXBOX
• ffmodstd

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interpolating polynomials from their values
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Efficient algorithm for Toeplitz plus Hankel matrices
• A probabilistic remark on algebraic program testing
• The interpolation problem for \(k\)-sparse polynomials and character sums
• The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators
• Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
• Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm
• Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
• Solving sparse linear equations over finite fields
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Computational Complexity of Sparse Rational Interpolation
• A Complete Implementation for Computing General Dimensional Convex Hulls
• Dagwood
• Sparse Polynomial Interpolation in Nonstandard Bases
• Shift-register synthesis and BCH decoding

This page was built for publication: Early termination in sparse interpolation algorithms