Title
Sparse interpolation of multivariate rational functionsSparse interpolation of multivariate rational functions
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Research group
Computational Mathematics
Publication type
article
Publication
Amsterdam,
Subject
Computer. Automation
Source (journal)
Theoretical computer science. - Amsterdam
Volume/pages
412(2011):16, p. 1445-1456
ISSN
0304-3975
ISI
000288730100002
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
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.
E-info
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000288730100002&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000288730100002&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000288730100002&DestLinkType=CitingArticles&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle