On the substitution of polynomial forms

ABSTRACT

The problem of devising efficient algorithms for computing Q(x1,...,xr-1, P(x1,...,xr-1)) where P and Q are multivariate polynomials is considered. It is shown that for polynomials which are completely dense an algorithm based upon evaluation and interpolation is more efficient than Horner's method. Then various characterizations for sparse polynomials are made and the subsequent methods are re-analyzed. In conclusion a test is devised which takes only linear time to compute and by which a decision can automatically be made concerning whether to use a substitution algorithm which exploits sparsity or one which assumes relatively dense inputs. This choice yields the method which takes the fewest arithmetic operations.

REFERENCES

• 1: Borodin, A., "Horner's rule is uniquely optimal", Theory of Machines and Computations, ed. by Z. Kohavi and A. Paz, pp. 45-59, 1971, Academic Press
• 2: 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]
• 3: George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971 [doi>10.1145/321662.321666]
• 4: Collins, G. E., "The SAC-1 polynomial system", University of Wisconsin, Comp. Sci. Tech. Report No. 115, March, 1971
• 5: Gentleman, W. M., "Optimal multiplication chains for computing a power of a symbolic polynomial", Mathematics of Computation, vol. 26, no. 120, pp. 935-940.
• 6: Andrew D. Hall, Jr., The ALTRAN system for rational function manipulation - a survey, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.153-157, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806280]
• 7: Horowitz, E., "The efficient calculation of polynomial powers", J.CSS October, 1973
• 8: Horowitz, E. and Sahni, S., "On the computation of powers of a class of polynomials", C.S. Tech. Report No. 72-143, Cornell University, Ithaca, New York, August, 1972
• 9: Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, March 1971
• 10: Horowitz, E., "On the Substitution of Polynomial Forms", Cornell Computer Science Technical Report 73-160, Jan. 1963

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.0 General

General Terms:
Algorithms, Theory