zbMATH — the first resource for mathematics

On exact and approximate interpolation of sparse rational functions. (English) Zbl 1190.65019
Brown, C. W. (ed.), ISSAC 2007. Proceedings of the 32nd international symposium on symbolic and algebraic computation (ISSAC 2007), Waterloo, ON, Canada, July 29–August 1, 2007. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-59593-743-8). 203-210 (2007).
Summary: 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. Randomization and early termination strategies are exploited to minimize the number of black box evaluations. In addition, rational number coefficients are recovered from modular 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 rational 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 benchmark implementation.
For the entire collection see [Zbl 1143.68004].
Reviewer: Reviewer (Berlin)

65D05 Numerical interpolation
68W30 Symbolic computation and algebraic computation