Skip to content

On the number of nonscalar multiplications necessary to evaluate polynomials

Authors: Michael S. Paterson; Larry J. Stockmeyer
Year: 1973
Venue: SIAM Journal on Computing

status: auto

Links: DOI

Abstract

We present algorithms which use only $O(\sqrt n )$ nonscalar multiplications (i.e. multiplications involving “x” on both sides) to evaluate polynomials of degree n, and proofs that at least $\sqrt n $ are required. These results have practical application in the evaluation of matrix polynomials with scalar coefficients, since the “matrix $ \times $ 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.
Source: crossref

SoK reference [62]

M. S. Paterson and L. J. Stockmeyer, “On the number of nonscalar multiplications necessary to evaluate polynomials,” SIAM Journal on Computing, vol. 2, no. 1, pp. 60–66, 1973.

Listed on the reference page of the site.

Files

No local PDF in the archive.


Database key: on-the-number-of-nonscalar-multiplications-necessary-to-evaluate · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set on-the-number-of-nonscalar-multiplications-necessary-to-evaluate COLUMN VALUE