On exact and approximate interpolation of sparse rational functions

The black box algorithm for separating the numerator from the denominator of a multivariate rational function can be combined with sparse multivariate polynomial interpolation algorithms to interpolate a sparse rational function. Ran-domization and early termination strategies are exploited to minimize the number of black box evaluations. In addi-tion, rational number coefficients are recovered from modu-lar images by rational vector recovery. The need for separate numerator and denominator size bounds is avoided via self-correction, and the modulus is minimized by use of lattice basis reduction, a process that can be applied to sparse ra-tional function vector recovery itself. Finally, one can deploy the sparse rational function interpolation algorithm in the hybrid symbolic-numeric setting when the black box for the rational function returns real and complex values with noise. We present and analyze five new algorithms for the above problems and demonstrate their effectiveness on a bench-mark implementation