Evaluation of polynomials with super-preconditioning

ABSTRACT

In an effort to understand the complexity of arithmetic computation, a number of researchers [1,5,7,8,9,11] have studied the following question: Given a polynomial f(x), Find a minimal cost straightline program that computes f(x).@@@@ In this paper this question is generalized to the following question: Given a polynomial f(x) and an operator &Dgr; that maps polynomials to sets of polynomials, Find a minimal cost straightline program that computes some h(x) &egr; &Dgr;(f(x)).

REFERENCES

• 1: E. G. Belaga. Some problems involved in the computation of polynomials. Dokl. Akad. Nauk SSSR 123:775-777, 1958.
• 2: Allan Borodin , Stephen Cook, On the number of additions to compute specific polynomials (Preliminary Version), Proceedings of the sixth annual ACM symposium on Theory of computing, p.342-347, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803913]
• 3: W. LeVeque. Topics in Number Theory, Volume II. Addison-Wesley, 1956.
• 4: Y. V. Linnik. On the least prime number in an arithmetic progression I: The basic theorem. Mat. Sbornik 15:139-178, 1944.
• 5: R. J. Lipton. Polynomials with 0-1 coefficients that are hard to compute. Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 6-10, 1975.
• 6: A. V. Malyshew. Yu. V. Linnik's works in number theory. Acta Arith. 27:3-10, 1975.
• 7: T. S. Motzkin. Evaluation of polynomials and evaluation of rational functions. Bulletin of the American Mathematical Society 61:163, 1955.
• 8: M. S. Paterson and L. J. Stockmeyer. On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM Journal of Computing 2:60-66, 1973.
• 9: V. Strassen. Polynomials with rational coefficients which are hard to compute. SIAM Journal of Computing 3:128-149, 1974.
• 10: E. Weiss. #Algebraic Number Theory. McGraw Hill, 1963.
• 11: S. Winograd. On the number of multiplications necessary to compute certain functions. Comm. Pure Appl. Math. 23:165-179, 1970.
• 12: I. Stewart. Galois Theory. Halsted Press, New York, 1973.

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

General Terms:
Theory