On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials

1973/03/01 by Michael S. Paterson, Larry J. Stockmeyer · 315 citations
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Algebra over a field #Arithmetic #Combinatorics #Degree (music) #Discrete mathematics #Mathematical proof #Mathematics #Matrix (chemical analysis) #Matrix multiplication #Numerical Methods and Algorithms #Polynomial and algebraic computation #Pure mathematics

paper · doi:10.1137/0202007

published in SIAM Journal on Computing 2(1), 60-66 (Society for Industrial and Applied Mathematics)

openalex publication_date 1973/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25

Abstract

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.

Cited by

• Evaluating parametric holonomic sequences using rectangular splitting
• Improving Matrix Exponential for Generative AI Flows: A Taylor-Based Approach Beyond Paterson--Stockmeyer
• Efficient Mod Approximation and Its Applications to CKKS Ciphertexts
• On a fast and nearly division-free algorithm for the characteristic polynomial
• Polynomial evaluation over finite fields: new algorithms and complexity bounds
• Fast Computation of the N-th Term of a q-Holonomic Sequence and Applications
• On the Exponentiation of Interval Matrices
• HEIR: A Universal Compiler for Homomorphic Encryption
• A point counting algorithm using cohomology with compact support
• Fast (Multi-)Evaluation of Linearly Recurrent Sequences: Improvements and Applications
• A scaling and recovering algorithm for the matrix φ-functions
• The Polar Express: Optimal Matrix Sign Methods and Their Application to the Muon Algorithm
• An improved algorithm to compute the exponential of a matrix
• Software Engineering and complexity in effective Algebraic Geometry
• Implicit purification for temperature-dependent density matrices
• Factorization of the tenth Fermat number
• Computing isomorphisms and embeddings of finite fields
• The functions erf and erfc computed with arbitrary precision and explicit error bounds

Related

• Chunky and Equal-Spaced Polynomial Multiplication
• Beating binary powering for polynomial matrices
• Fast Operations on Linearized Polynomials and their Applications in Coding Theory
• Intra-Basis Multiplication of Polynomials Given in Various Polynomial Bases
• Accurate Evaluation of Polynomials