Title




Sparse interpolation of multivariate rational functions


Author






Abstract




Consider the black box interpolation of a τsparse, nvariate rational function f, where τ is the maximum number of terms in either numerator or denominator. When numerator and denominator are at most of degree d, then the number of possible terms in f is O(dn) and explodes exponentially as the number of variables increases. The complexity of our sparse rational interpolation algorithm does not depend exponentially on n anymore. It still depends on d because we densely interpolate univariate auxiliary rational functions of the same degree. We remove the exponent n and introduce the sparsity τ in the complexity by reconstructing the auxiliary functions coefficients via sparse multivariate interpolation. The approach is new and builds on the normalization of the rational functions representation. Our method can be combined with probabilistic and deterministic components from sparse polynomial black box interpolation to suit either an exact or a finite precision computational environment. The latter is illustrated with several examples, running from exact finite field arithmetic to noisy floating point evaluations. In general, the performance of our sparse rational black box interpolation depends on the choice of the employed sparse polynomial black box interpolation. If the early termination BenOr/Tiwari algorithm is used, our method achieves rational interpolation in O(τd) black box evaluations and thus is sensitive to the sparsity of the multivariate f. 


Language




English


Source (journal)




Theoretical computer science.  Amsterdam


Publication




Amsterdam
:
2011


ISSN




03043975


Volume/pages




412
:16
(2011)
, p. 14451456


ISI




000288730100002


Full text (Publisher's DOI)





