A deterministic algorithm for sparse multivariate polynomial interpolation

ABSTRACT

An efficient deterministic polynomial time algorithm is developed for the sparse polynomial interpolation problem. The number of evaluations needed by this algorithm is very small. The algorithm also has a simple NC implementation.

REFERENCES

• 1: L M Adleman , H W Lenstra, Finding irreducible polynomials over finite fields, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.350-355, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12166]
• 2: E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970) 713-735.
• 3: R. E. Blahut, The Theory and Practice of Error Control Codes, Addison-Wesley Publishing Co., 1983.
• 4: J. Edmonds, Systems of distinm representatives and linear algebra, .I. Res. Nat. Bur. Stand. 713 (1967) 241-245.
• 5: R. J. Evans anti I. M. lsaacs. Generalized Vandermonde determinants and roots of unity of prime order, Proc. of the AMS 5II (1976) 51-54.
• 6: Shmuel Gal and Yuri Breitbart, A method for obtaining all the solutions of a perfect matching problem, Technical Report No. 016, IBM israel Scientific Center (May 1974).
• 7: J. wm zur Gathen, Parallel powering, Proc. of the 25th iEEE Symposium on Foundations of Computer Science, pp. 31-36, 1984.
• 8: Dima Grigoriev , Marek Karpinski, The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents is in $NC$, University of Bonn, 1986
• 9: D. Yu. Grigoriev and M. Karpinski, "File matching problem for bipartite graphs with poiynonlialty bounded permanents is in NC, Proc. o1' the 28th I EEE Symposium ~n Foundations of Computer Science, pp. 166-172, 1987.
• 10: E. Kaltofen, Factorization of polynomials given by straight line programs, manuscript, 1986.
• 11: E. Kaltofen and B. Trager, Sparse factorization and rational function interpolation of polynomials given by black-boxes for their evaluation, manuscript, 1987.
• 12: R. Loos, Computing rational zeros of integral polynomials by p-adic expansion, SIAM .I. Comp. 12 (1983) 286-293.
• 13: L. Lovasz, On determinants, matchings, and random algorithms, Fttttdattu'tttal.c of Com?uting Theory, edited by L. Budach, Akademia-Verlag, Berlin (1979).
• 14: 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]
• 15: P. Tiwari, Parallel algorithms for instances of linear matroid parity with a small number of solutions, RC 12766, IBM T, J. Watson Research Center, May 1987.
• 16: P. Tiwari, Algorithms for multivariate polynomial interpolation, manuscript, June 1987.
• 17: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
• 18: R. E. ZippeI, Interpolating polynomials from their values, manuscript, 1988.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

General Terms:
Algorithms, Theory