Modular rational sparse multivariate polynomial interpolation

ABSTRACT

The problem of interpolating multivariate polynomials whose coefficient domain is the rational numbers is considered. The effect of intermediate number growth on a speeded Ben-Or and Tiwari algorithm is studied. Then the newly developed modular algorithm is presented. The computing times for the speeded Ben-Or and Tiwari and the modular algorithm are compared, and it is shown that the modular algorithm is markedly superior.

REFERENCES

• 1: 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]
• 2: BLAHUT, R. Theory and Practice of Error Correcting Codes. Addison and Wesley, Reading, Mass., 1983.
• 3: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 4: CANTOR, D. G., ANO ZASSENiiAVS, H. A new algorithm for factoring polynomials over finite fields. Mathematics of Computation 36, 154 (April 1981), 587-592.
• 5: GRIaORYr. V, D. Y., AND KARPINSKI, M. The matching problem for bipartite graphs with polynomial bounded determinants is in NC. In Proc. 28th IEEE Symp. Foundations Comp. Science (1987), pp. 167-172.
• 6: KALTOFEN, E., LAKSHMAN, Y. N., AND WI- LEY, J. M. Efficient sparse multivariate poynomial interpolation algorithms. Manuscript, December 1989.
• 7: 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]
• 8: Erich Kaltofen , Yagati N. Lakshman, Improved Sparse Multivariate Polynomial Interpolation Algorithms, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.467-474, July 04-08, 1988
• 9: MAssE'f, J. Shift-register synthesis and BCH coding. IEEE Trans. Inform. Theory IT-15 (1969), 122-127.
• 10: 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]
• 11: 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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms