MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Fast evaluation of polynomials

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.

-
Perhaps polynomial chains are what you are looking for, see for example section 4.6.4 of The Art of Computer Programming. – Pontus von Brömssen Jul 4 2011 at 19:46

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.

-
Oh ! I did not know this method's name, thank you ! :-) I was actually interested in the case in which you have full information on the polynomial. Is there any computation you could do on it that would let you find the minimum number of operations to evaluate this specific polynomial ? :-) – Nathann Cohen Jul 4 2011 at 16:15
Nathann Cohen, what do you mean by 'full information'? – quid Jul 4 2011 at 16:20
My question probably was not accurate enough, so I appended a comment at the end. I am not looking for an algorithm that would be able to evaluate a polynomial, but an algorithm which -- given a polynomial -- would output "the best algorithm possible to evaluate this polynomial", using the least number of additions/muliplications possible. It would know the exact coefficients of this polynomial and can spend as much time as it likes trying to find out the best sequence of addition/multiplications to evaluate it. This way, this polynomial can be evaluated very often afterwards at no cost ! :-) – Nathann Cohen Jul 4 2011 at 16:23
You are basically asking about the arithmetical circuit complexity of the polynomial. For multivariate polynomials, this question leads to extremely hard problems in complexity, see en.wikipedia.org/wiki/… for a start. Even in the univariate case, I doubt there is any general method to compute the complexity of specific polynomials. – Emil Jeřábek Jul 4 2011 at 16:27
Nathann Cohen, thank you for the clarification. Not sure if I missed your p.s. to the question or it and my comment happened in parallel. – quid Jul 4 2011 at 16:28
show 1 more comment

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".

-

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

-

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.

-

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).

-
 I also cite an answer involving differencing below. Can you say how forward differencing differs from kth order differences? Gerhard "Not Sure About Differing Differences" Paseman, 2011.07.14 – Gerhard Paseman Jul 14 2011 at 17:31