Optimal multiplication chains for computing a power of a symbolic polynomial

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

• 1: Gentleman, W. M. and Sande, G. "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, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997