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