Question

Hello everybody !

I was reading a book on geometry which taught me that one could compute the volume of a simplex through the determinant of a matrix, and I thought (I'm becoming a worse computer scientist each day) that if the result is exact this may not be the computationally fastest way possible to do it.

Hence, the following problem : if you are given a polynomial in one (or many) variables $\alpha_1 x^1 + \dots + \alpha_n x^n$, what is the cheapest way (in terms of operations) to evaluate it ?

Indeed, if you know that your polynomial is $(x-1)^{1024}$, you can do much, much better than computing all the different powers of $x$ and multiply them by their corresponding factor.

However, this is not a problem of factorization, as knowing that the polynomial is equal to $(x-1)^{1024} + (x-2)^{1023}$ is also much better than the naive evaluation.

Of course, multiplication and addition all have different costs on a computer, but I would be quite glad to understand how to minimize the "total number of operations" (additions + multiplications) for a start ! I had no idea how to look for the corresponding litterature, and so I am asking for your help on this one :-)

Thank you !

Nathann

P.S. : I am actually looking for a way, given a polynomial, to obtain a sequence of addition/multiplication that would be optimal to evaluate it. This sequence would of course only work for THIS polynomial and no other. It may involve working for hours to find out the optimal sequence corresponding to this polynomial, so that it may be evaluated many times cheaply later on.

Answer 1

If the polynomial is given as $\alpha_0x^0+\dots+\alpha_nx^n$ and you do not know a priori anything about the $\alpha_i$’s, then you can’t do better than Horner’s scheme (which takes $n$ additions and multiplications). If you know that the polynomial is sparse and you are given a list of nonzero coefficients, you can evaluate the individual terms using repeated squaring (this takes about $k$ additions and $O(k\log n)$ multiplications, where $k$ is the number of nonzero terms). Other information about the polynomial may also help in principle, such as some sort of symmetries in the coefficient list.

Answer 2

The simplest version of this question is: what is the quickest way to evaluate $x^n?$ For $n = 2^k,$ $k$ repeated squarings is obviously best, but for more complicated $n$ I believe that finding the optimum is very hard -- see Knuth, vol 2 for (much) more on these so-called "multiplication trees".

Answer 3

The cheapest way of finding the value of a polynomial, given unlimited preprocessing resources, is to look up the precalculated value in the table. However, if you know you are going to need several more values evaluated at successive intervals, you might try a method similar to that desired by Charles Babbage: differences. Namely, store the value and the the n kth order differences (similar to evaluations at derivatives) for point x, and then use n additions to derive the differences and value for the polynomial at the point x+1. If you need to loop through to evaluate the polynomial at successive integers, this gets those values with O(n) additions per evaluation point.

(Of course needing random or real access to the polynomial will require something different, but you might find storing values at derivatives useful for evaluating the polynomial at near by points, especially if multiplication is expensive..)

Gerhard "Email Me About System Design" Paseman, 2011.07.04

Answer 4

Consider the polynomial $f(x) = nx$, where $n$ is an integer. Here are two algorithms which will evaluate this polynomial:

Algorithm 1. Multiply $n$ by $x$.

Algorithm 2. Calculate $x + x + \ldots + x$.

Which is more efficient? Given fixed $n$, this depends on your processor architecture. And this is just about the simplest case imaginable -- we only have one variable, the polynomial is linear, and we're not even thinking about pipelined calculations yet. Also, as mentioned before, you are going to have to formalize the problem in some way which eliminates the "algorithm" consisting of a table giving the value at each machine-sized number. As stated, I don't think the question is answerable.

Answer 5

If you want to evaluate the polynomial at a lot of equidistant points, you can do "forward differencing"; here are 3 slides explaining the method: http://zach.in.tu-clausthal.de/teaching/info2_11/folien/evaluating%20a%20polynomial%20at%20equidistant%20points.pdf (they are in German, but I believe you'll still get it).