Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases

DOI10.1016/S0747-7171(03)00087-7zbMath1074.68078MaRDI QIDQ1878479

Wen-Shin Lee, Mark W. Giesbrecht, Erich L. Kaltofen

Publication date: 20 August 2004

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

zbMATH Keywords

Chebyshev basisSparse polynomialEarly terminationPochhammer basisSparse interpolationSparse shifts

Mathematics Subject Classification ID

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

Related Items (4)

Early termination in sparse interpolation algorithms ⋮ A nearly optimal algorithm to decompose binary forms ⋮ Reconstruction algorithms for sums of affine powers ⋮ Interpolation of polynomials given by straight-line programs

Uses Software

• FOXBOX

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• A probabilistic remark on algebraic program testing
• Algorithms for computing sparse shifts for multivariate polynomials
• Early termination in sparse interpolation algorithms
• Sparse shifts for univariate polynomials
• Approximate formulas for some functions of prime numbers
• 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
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Generalized Vandermonde Determinants and Roots of Unity of Prime Order
• Computational Complexity of Sparse Rational Interpolation

This page was built for publication: Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases