Polynomial Multiplication, Powers and Asymptotic Analysis: Some Comments

This paper examines multiplication and powering of dense symbolic polynomials, in one or several variables, with “nongrowing” coefficients (e.g., coefficients in a finite field). We use a “completely dense” model for polynomials, in order to present worst-case analyses. In this context, the use and abuse of asymptotic analysis techniques is discussed. Six algorithms for computing polynomial powers are analyzed in terms of the time required for execution on a typical digital computer, and procedures are derived for choosing the fastest algorithm, exactly, as a function of degree, number of variables, and power to be computed. The case of sparse polynomials is discussed in a separate paper [6].