Efficient polynomial substitutions of a sparse argument
William H. Rowan · ACM SIGSAM Bulletin · 1981
Methods are presented for taking powers of symbolic polynomials and substituting them into univariate polynomials with scalar coefficients. It is shown that the size of the result is a sharp lower bound on the number of coefficient multiplications required to raise a completely sparse polynomial to a power. Other theoretical results prove the optimality or near-optimality of the methods given, in terms of numbers of coefficient operations, under the condition of complete sparsity of the argument.