1973/03/01 by Michael S. Paterson, Larry J. Stockmeyer · 15 citations
Computer Science · Mathematics · #Polynomial and algebraic computation #Numerical Methods and Algorithms #Advanced Optimization Algorithms Research
paper · doi:10.1137/0202007
We present algorithms which use only O(√ n ) nonscalar multiplications (i.e. multiplications involving “x” on both sides) to evaluate polynomials of degree n, and proofs that at least √ n are required. These results have practical application in the evaluation of matrix polynomials with scalar coefficients, since the “matrix × matrix” multiplications are relatively expensive, and also in determining how many multiplications are needed for polynomials with rational coefficients, since multiplications by integers can in principle be replaced by several additions.