Sparse interpolation of multivariate rational functions. (English) Zbl 1211.65014

Summary: Consider the black box interpolation of a \(\tau \)-sparse, \(n\)-variate rational function \(f\), where \(\tau \) 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(d^n)\) 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 \(\tau \) in the complexity by reconstructing the auxiliary function’s coefficients via sparse multivariate interpolation.
The approach is new and builds on the normalization of the rational function’s 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(\tau d)\) black box evaluations and thus is sensitive to the sparsity of the multivariate \(f\).


65D05 Numerical interpolation


FOXBOX; ffmodstd
Full Text: DOI


[1] Allouche, H.; Cuyt, A., On the structure of a table of multivariate rational interpolants, Constr. approx., 8, 69-86, (1992) · Zbl 0764.41008
[2] Clausen, M.; Dress, A.; Grabmeier, J.; Karpinski, M., On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields, Theoret. comput. sci., 84, 2, 151-164, (1991) · Zbl 0737.65002
[3] Cuyt, A., A recursive computation scheme for multivariate rational interpolants, SIAM J. numer. anal., 24, 228-238, (1987) · Zbl 0616.65012
[4] Cuyt, A.; Lee, W.-s., A new algorithm for sparse interpolation of multivariate polynomials, Theoret. comput. sci., 409, 2, 180-185, (2008) · Zbl 1181.68328
[5] de Kleine, J.; Monagan, M.; Wittkopf, A., Algorithms for the non-monic case of the sparse modular gcd algorithm, (), 124-131 · Zbl 1360.11145
[6] DeMillo, R.A.; Lipton, R.J., A probabilistic remark on algebraic program testing, Inform. process. lett., 7, 4, 193-195, (1978) · Zbl 0397.68011
[7] Díaz, A.; Kaltofen, E., Foxbox: a system for manipulating symbolic objects in black box representation, (), 30-37 · Zbl 0918.68049
[8] Giesbrecht, M.; Labahn, G.; Lee, W.-s., Symbolic-numeric sparse interpolation of multivariate polynomials (extended abstract), (), 116-123 · Zbl 1356.65032
[9] Giesbrecht, M.; Labahn, G.; Lee, W.-s., Symbolic-numeric sparse interpolation of multivariate polynomials, J. symbolic comput., 44, 8, 943-959, (2009) · Zbl 1167.65003
[10] Grigoriev, D.; Karpinski, M.; Singer, M.F., Computational complexity of sparse rational interpolation, SIAM J. comput., 23, 1, 1-12, (1994) · Zbl 0802.68060
[11] Grigoriev, D.Y.; Karpinski, M., Algorithms for sparse rational interpolation, (), 7-13 · Zbl 0920.65004
[12] Grigoriev, D.Y.; Karpinski, M.; Singer, M.F., Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM J. comput., 19, 6, 1059-1063, (1990) · Zbl 0711.68059
[13] Grigoriev, D.Y.; Karpinski, M.; Singer, M.F., Interpolation of sparse rational functions without knowing bounds on exponents, (), 840-846
[14] Javadi, S.M.M.; Monagan, M., Parallel sparse polynomial interpolation over finite fields, (), 160-168
[15] Kaltofen, E., Greatest common divisors of polynomials given by straight-line programs, J. ACM, 35, 1, 231-264, (1988) · Zbl 0642.68058
[16] Kaltofen, E.; Lee, W.-s., Early termination in sparse interpolation algorithms, J. symbolic comput., 36, 3-4, 365-400, (2003) · Zbl 1074.68080
[17] Kaltofen, E.; Lee, W.-s.; Lobo, A.A., Early termination in ben-or/tiwari sparse interpolation and a hybrid of zippel’s algorithm, (), 192-201 · Zbl 1326.68358
[18] Kaltofen, E.; Trager, B., Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, J. symbolic comput., 9, 3, 301-320, (1990) · Zbl 0712.12001
[19] Kaltofen, E.; Yang, Z., On exact and approximate interpolation of sparse rational functions, (), 203-210 · Zbl 1190.65019
[20] Kaltofen, E.; Yang, Z.; Zhi, L., On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms, (), 11-17
[21] Khodadad, S.; Monagan, M., Fast rational function reconstruction, (), 184-190 · Zbl 1356.11094
[22] Monagan, M., Maximal quotient rational reconstruction: an almost optimal algorithm for rational reconstruction, (), 243-249 · Zbl 1134.68602
[23] Olesh, Z.; Storjohann, A., The vector rational function reconstruction problem, (), 137-149
[24] Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 701-717, (1980) · Zbl 0452.68050
[25] von zur Gathen, J.; Gerhard, J., Modern computer algebra, (1999), Cambridge University Press · Zbl 0936.11069
[26] Zippel, R., Probabilistic algorithms for sparse polynomials, (), 216-226
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.