Publication
Title
Sparse interpolation of multivariate rational functions
Author
Abstract
Consider the black box interpolation of a τ-sparse, n-variate 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 Ben-Or/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
0304-3975
Volume/pages
412:16(2011), p. 1445-1456
ISI
000288730100002
Full text (Publisher's DOI)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 18.06.2011
Last edited 05.09.2017
To cite this reference