Computational Complexity of Sparse Rational Interpolation

DOI10.1137/S0097539791194069MaRDI QIDQ4286224zbMATH OpenFDO

Authors Michael F. Singer, Dima Grigoriev, Marek Karpinski

Publication date 27 April 1994

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539791194069

zbMATH Keywords

computational complexityinterpolationarithmetic operationssparse rational functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Real rational functions (26C15)

Cited in

(16)

• Sparse shifts for univariate polynomials
• Reconstructing rational functions with \texttt{FireFly}
• Interpolation of dense and sparse rational functions and other improvements in \texttt{FireFly}
• Balancing act: multivariate rational reconstruction for IBP
• Early termination in sparse interpolation algorithms
• Noisy interpolation of sparse polynomials in finite fields
• scientific article; zbMATH DE number 917814 (Why is no real title available?)
• A Wronskian approach to the real \(\tau\)-conjecture
• Lower complexity bounds for interpolation algorithms
• Deterministically testing sparse polynomial identities of unbounded degree
• Sparse interpolation of multivariate rational functions
• Computing Sparse Representations of Systems of Rational Fractions
• Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases
• Computability of the additive complexity of algebraic circuits with root extracting
• scientific article; zbMATH DE number 421669 (Why is no real title available?)
• Zero testing of \(p\)-adic and modular polynomials

This page was built for publication: Computational Complexity of Sparse Rational Interpolation

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