On exact and approximate interpolation of sparse rational functions

ABSTRACT

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. domization 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 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 sparse rational function interpolation algorithm in the hybrid symbolic-numeric setting when the black box for the 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 mark implementation.

REFERENCES

• 1: Becuwe, S., Cuyt, A., and Verdonk, B. Multivariate rational interpolation of scattered data. In Large-Scale Scientific Computing (Heidelberg, Germany, 2004), I. Lirkov, S. Margenov, J. Wasniewski, and Y. Plamen, Eds., vol. 2907 of Lect. Notes Comput. Sci., Springer Verlag, pp. 204--213.
• 2: Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
• 3: DeMillo, R.A., and Lipton, R.J. probabilistic remark on algebraic program testing. Information Process. Letters 7,4 (1978), 193--195.
• 4: Angel Díaz , Erich Kaltofen, FOXBOX: a system for manipulating symbolic objects in black box representation, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.30-37, August 13-15, 1998, Rostock, Germany [doi>10.1145/281508.281538]
• 5: Dumas, J.-G. Ed. ISSAC MMVI Proc. 2006 Internat. Symp. Symbolic Algebraic Comput. (New York, N.Y., 2006), ACM Press.
• 6: Joachim Von Zur Gathen , Jurgen Gerhard, Modern Computer Algebra, Cambridge University Press, New York, NY, 2003
• 7: Mark Giesbrecht , George Labahn , Wen-shin Lee, Symbolic-numeric sparse interpolation of multivariate polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145792]
• 8: Dima Grigoriev , Marek Karpinski , Michael F. Singer, Computational Complexity of Sparse Rational Interpolation, SIAM Journal on Computing, v.23 n.1, p.1-12, Feb. 1994 [doi>10.1137/S0097539791194069]
• 9: Kai, H. Rational function approximation and its ill-conditioned property. In Wang and Zhi {26}, pp.47--53. Preliminary version in {25}, pp. 62--64.
• 10: Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988 [doi>10.1145/42267.45069]
• 11: Erich Kaltofen, Asymptotically fast solution of Toeplitz-like singular linear systems, Proceedings of the international symposium on Symbolic and algebraic computation, p.297-304, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190431]
• 12: Erich Kaltofen, Analysis of Coppersmith's block Wiedemann algorithm for the parallel solution of sparse linear systems, Mathematics of Computation, v.64 n.210, p.777-806, April 1995 [doi>10.2307/2153451]
• 13: Erich Kaltofen , Wen-shin Lee, Early termination in sparse interpolation algorithms, Journal of Symbolic Computation, v.36 n.3-4, p.365-400, September 2003 [doi>10.1016/S0747-7171(03)00088-9]
• 14: Erich Kaltofen , Wen-shin Lee , Austin A. Lobo, Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.192-201, July 2000, St. Andrews, Scotland [doi>10.1145/345542.345629]
• 15: Kaltofen, E., and Rolletschek, H. Computing greatest common divisors and factorizations in quadratic number fields. Math. Comput. 53,188 (1989), 697--720.
• 16: Erich Kaltofen , Barry M. Trager, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Journal of Symbolic Computation, v.9 n.3, p.301-320, March 1990 [doi>10.1016/S0747-7171(08)80015-6]
• 17: Erich Kaltofen , Zhengfeng Yang , Lihong Zhi, Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145799]
• 18: Kaltofen, E., Yang, Z., and Zhi, L. On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms, 2007. Manuscript in preparation.
• 19: Kaltofen, E., Yang, Z., and Zhi, L. Structured low rank approximation of a Sylvester matrix. In Wang and Zhi {26}, pp.69--83. Preliminary version in {25 }, pp. 188--201.
• 20: J. C. Lagarias, The computational complexity of simultaneous diophantine approximation problems, SIAM Journal on Computing, v.14 n.1, p.196-209, Feb. 1985 [doi>10.1137/0214016]
• 21: Michael Monagan, Maximal quotient rational reconstruction: an almost optimal algorithm for rational reconstruction, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.243-249, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005321]
• 22: Olesh, Z., and Storjohann, A. The vector rational function reconstruction problem, Sept. 2006. Manuscript, 14 pages.
• 23: Park, H., Zhang, L., and Rosen, J. B. Low rank approximation of a Hankel matrix by structured total least norm. BIT 39,4 (1999), 757--779.
• 24: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 25: Wang, D., and Zhi, L. Eds. Internat. Workshop on Symbolic-Numeric Comput. SNC 2005 Proc.(2005). Distributed at the Workshop in Xi'an, China, July 19-21.
• 26: Dongming Wang , Li-Hong Zhi, Symbolic-Numeric Computation (Trends in Mathematics), Birkhäuser Basel, 2007
• 27: Paul S. Wang , M. J. T. Guy , J. H. Davenport, P-adic reconstruction of rational numbers, ACM SIGSAM Bulletin, v.16 n.2, p.2-3, May 1982 [doi>10.1145/1089292.1089293]
• 28: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
• 29: Richard Zippel, Interpolating polynomials from their values, Journal of Symbolic Computation, v.9 n.3, p.375-403, March 1990 [doi>10.1016/S0747-7171(08)80018-1]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems

General Terms:
Algorithms, Experimentation

Keywords:
early termination, hybrid symbolic-numeric computation, lattice basis reduction, rational vector recovery, sparse rational function interpolation