Computational Complexity of Sparse Rational Interpolation

DOI10.1137/S0097539791194069zbMath0802.68060MaRDI QIDQ4286224

Michael F. Singer, Dima Yu. Grigoriev, Marek Karpinski

Publication date: 27 April 1994

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

zbMATH Keywords

interpolationcomputational complexityarithmetic 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)

Related Items (12)

Early termination in sparse interpolation algorithms ⋮ Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases ⋮ Computability of the additive complexity of algebraic circuits with root extracting ⋮ Sparse shifts for univariate polynomials ⋮ Interpolation of dense and sparse rational functions and other improvements in \texttt{FireFly} ⋮ Balancing act: multivariate rational reconstruction for IBP ⋮ Sparse interpolation of multivariate rational functions ⋮ Reconstructing rational functions with \texttt{FireFly} ⋮ A Wronskian approach to the real \(\tau\)-conjecture ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Noisy interpolation of sparse polynomials in finite fields ⋮ Zero testing of \(p\)-adic and modular polynomials

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