Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Optimal multiplication chains for computing a power of a symbolic polynomial

Author: W. Morven Gentleman
Journal: Math. Comp. 26 (1972), 935-939
MSC: Primary 68A15
MathSciNet review: 0314303
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper shows that in a certain model of symbolic manipulation of algebraic formulae, the simple method of computing a power of a symbolic polynomial by repeated multiplication by the original polynomial is, in essence, the optimal method.

References [Enhancements On Off] (What's this?)

  • [1] W. M. Gentleman & G. Sande, ``Fast Fourier transforms--for fun and profit,'' Proceedings of the 1966 Fall Joint Computer Conference, AFIPS, Spartan Books, Washington, 1966, pp. 563-578.
  • [2] Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 0378456

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 68A15

Retrieve articles in all journals with MSC: 68A15

Additional Information

Keywords: Symbolic algebraic manipulation, optimal multiplication chains, complexity
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society