On the Evaluation of Powers and Related Problems (Preliminary Version)

Jul 10, 2026

Uploaded by Patrick

Evaluation of powers via addition chains for non-negative integer matrices is studied through the function L(p,q,N), which measures the worst-case minimum number of vector-addition steps needed to compute all p rows of a p-by-q matrix with entries from {0,1,…,N}. The work motivates applications to optimal multiplication of multivariate sparse polynomials and to simulating linear fixed-point transformations using only additions. It develops a constructive graph-theoretic framework for Lupanov-style bounds and presents Theorem 1 under structural size conditions.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages6

Reading Time15 min

AccessFree to download

Introduction

Lupanov's Problem

Graph-theoretic model and realization

Transformation of realizing graphs

ON THE EVALUATION OF POWERS AND RELATED PROBLEMS (Preliminary Version) by Nicholas PippengerMathematical Sciences DepartmentIBM Thomas J.Watson Research CenterYorktown Heights,N.Y.10598 # Introduction Let M be a p-by-q matrix of non-negative inte-gers.We shall consider the problem of obtaining thep rows of M by computations in which 1.the zero vector(0,...,0)and the qunit vectors(1,.…,0),……,(0,.,1)are availableat no cost; 2.the sum of two(not necessarily dstinct)previously computed vectors is available at a cost of Such a computation is called an addition chain for M.Let (M) denote the minimum possible number of stepsin an addition chain for M.Let L(p,q,N)denotethe maximum of (M)over al¹p-by-q matrices Mwhose entries are drawn from {0,1,…,N}. Let us mention two applications of this problem. seek to compute the p monomials starting from the q indeterminates x₁,x₂,…x,and using the minimum possible number of two-operandmultiplications. This problem has obvious relevance for evaluatingsparse multivariate polynomials. Another applicationemerges upon "taking the logarithm of the problem". Problem 2:We are given a matrix M as before.We M1×1+M12×2+…+M1q×qM21×1+M22×2 +…+M2q*qMp1×1+Mp2×2 +…+MPq*q, starting with the q indeterminates X1,X2,…×q'and using the minimum possible number of two-operandadditions. This problem arises in signal-processing applica- tions:we are called upon to perform a linear trans- formation whose coefficients are fixed-point numbers (which can be regarded as integers);if we have noMULTIPLY instruction in our machine,we must simulatescalar multiplication by addition.(This problemwould be more realistic if we allowed negative coeffi-cients,subtractions,and short shifts.These changeswould not affect our analysis or results in any sig-nificant way.) Many special cases of this problem have been con-sidered by various authors.The first of these was thecase p=1,q=1 proposed in 1937 by Scholz [1],whoobserved that log N≤L(1,1,N)≤2 log N. (In this paper,log denotes the binary logarithm,whileln denotes the natural logarithm.)Brauer [2]im-proved the upper bound to L(1,1,N)≤1og N and thus obtained an asymptotic formula for L(1,1,N).Erdös[3]worked out the next term in the expansion: In 1956,Lupanov [4]considered the case N=1.(Lupanov's problem was not formally equivalent to thiscase,but his ideas require only trivial modificationsfor application in the present context.)He showedthat if =2°()and q=2°(p) (1) (this condition says that the matrix is not "exponen-tially lopsided"),then Furthermore,he obtained (2) and thus an asymptotic formula for L(p,q,1),on the additional condition that (3) tend to 0 or ∞.Nechiporuk [5]weakened this condi-tion to require only that(3)tend to a member of aninfinite,but nowhere dense,set of rational numbers.His solution involves a "nonconstructive"averaging ar-gument.Below,we shall give a constructive solutionthat requires no condition on(3)and establishes(2)on the assumption of(1)alone. In 1963,Bel1man [6]posed the case p=1,andStraus [7]showed that for any fixed q, L(1,q,N)～log N. Finally,in 1969 Knuth[8]posed the case q=1,andYao [9]showed that for any fixed p, L(p,1,N)～log N. This result actually holds for p=o(1og log N).Below,we shall show that for p=n°(1), # Lupanov's Problem We shall develop our first theorem in a graph-theoretic setting introduced by Lupanov.Let r be anacyclic directed graph with p distinguished verticesand q distinguished verticesn₁…,npWe shall say that r realizes M if the number offor 1≤1≤pdfrected paths from n1 to⁵18 M1and 1≤jsq.Let '(M)denote the minimum possiblenumber of edges in a graph that realizes M.LetL'(p,q,N)denote the maximum of 8'(M)over allp-by-q matríces whose entries are drawn from {0,1,...N}. Theorem 1:If p=2°(9)and q=2°(P), sece DPpyq,1)-1(9per crea12e the branLeposeof M,then reverse the direction of all edges),wemay assume p≥q.The upper bound in the case

FAQs

What is an addition chain for a non-negative integer p-by-q matrix?

An addition chain is a computation model where the zero vector and the q qunit vectors are free, and each additional step computes the sum of two previously computed vectors at a cost of one step.

How are L(p,q,N) and L′(p,q,N) defined in the document?

L(p,q,N) is the maximum, over all p-by-q matrices with entries in {0,1,…,N}, of the minimum number of steps needed in an addition chain. L′(p,q,N) is defined similarly but uses a graph realization concept and measures the maximum over such matrices of the minimum number of edges in realizing acyclic directed graphs.

What is Lupanov’s problem approach used in this paper?

The paper presents a graph-theoretic setting where an acyclic directed graph with p inputs and q distinguished vertices realizes a matrix by counting directed paths. It then constructs a constructive solution that establishes upper bounds like those associated with Lupanov under conditions comparing the growth rates of p and q.

Jul 10, 2026

Uploaded by Patrick