Q: Efficient evaluation of multivariable polynomials

[Stan Thomas]

I need an efficient algorithm for evaluating multivariable polynomials.

For example, given two variables x1, and x2. I define the "2nd" order
polynomial in x1 and x2 to be:

P = a00 + a01*x1 + a02*x1^2 + a10*x2 + a11*x2*x1 + a12*x2*x1^2 +
a20*x2^2 + a21*x2^2*x1 + a22*x2^2*x1^2

P can be computed as follows (C pseudocode)

P = 0.0E0;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
P += a[i][j]*pow(x[0],i)*pow(x[1],j);
}
}

What I need is a computationally efficient algorithm for computing P
given the "Nth" order polynomial in M variables. Clearly the above
method is neither efficient nor easily extended to arbitrary order.

Thanks,
Stan

[Hans D. Mittelmann]

Hi,
Horner's method evaluates the single-variable polynomial
p(x)=a0 + a1*x +... + an*x^n
through
an' = an
for i=n-1(-1)0 do
ai' = ai + x*ai+1'
with p(x)=a0'
Just generalize that to the multivariable case with more nested loops.

--
Hans D. Mittelmann http://plato.la.asu.edu/
Arizona State University Phone: (602) 965-6595
Department of Mathematics Fax: (602) 965-0461
Tempe, AZ 85287-1804 email: mitte...@asu.edu