Fast Evaluation of Multivariate Polynomials

Is there a generalization of the polyval function to higher dimensions? I have looked just about everywhere and haven't come across one. I cooked up this recursive implementation, which I consider a good first cut, but it's not much to look at:

function f = ndpolyval(p, x)

N = size(x, 1);

if N > 1
    idx = repmat({':'}, 1, N);
    x2 = x(1:N - 1, :);
    M = size(p, N);
    z = zeros(M, 1);
    for i = 1:M
        idx{N} = i;
        z(i) = ndpolyval(p(idx{:}), x2);
    end
    p = z;
    x = x(end);
end

f = polyval(p, x);

This implementation has several issues. For starters, it only accepts one point, x. So if you want to evaluate your multivariate polynomial at multiple points, it will be very slow. It would also be nice if the function could return the gradient and Hessian of the polynomial.

Thanks,

Bill Woessner

Answer 1

[Sharon Dolberg]

I wrote a multidimensional polyval function, a bit different from the original polyval. May it assist the users:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [a,ErrV]=polyvalN(MatIn,TargetIn)
[n,m]=size(MatIn);
MatOut=sum(pagemtimes(reshape(MatIn',m,1,n),reshape(MatIn',1,m,n)),3);
TargetOut=sum(MatIn.*TargetIn)';
a=MatOut\TargetOut;
ErrV=MatIn*a-TargetIn;
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

This function takes in a matrix MatIn which already includes the approximated structure for a linear approximated function (polynom) which the coefficient (a) of the approximated function needs to be found according to the target values TargetIn

for example:

------------

We have 8 points on a box

X=[-1;1;-1;1;-1;1;-1;1];

Y=[-1;-1;1;1;-1;-1;1;1]*2;

Z=[-1;-1;-1;-1;1;1;1;1]*0.5;

The approximated function which we intend to find the coefficients for is:

MatIn=[ones(8,1), X , Y , Z , X.*Y , X.*Z , Y.*Z ];

The value in each point is given. We can use rand or any known values in each point. Just in order to check the function polyvalN, we'll use known a's

intentionally:

TargetIn= 7 + 6*X + 5*Y + 4*Z + 3*X.*Y + 2*X.*Z + 1*Y.*Z;

Now, is we pose MatIn,TargetIn to polyvalN , we expect to get a's

[7;6;5;...1]

-------------

Notes:1. MatIn should be nXm wherein n>=m

TargetIn should be nx1

2. The point represented by X,Y,Z are not necessarily be in a box

structure as in the example. Actually, they can also represent any

single-dimension/multidimensional location, as long as note 1 is kept, and that MatIn includes

the vectors in the approximation.

Answer 2

[John D'Errico]

You have clearly not looked quite EVERYWHERE. Had you done so, you might have found my polyfitn. In there, is a polyvaln code, which does perform evaluation of a polynomial for n variables.

Find the polyfitn tools on the File Exchange.

https://www.mathworks.com/matlabcentral/fileexchange/34765-polyfitn?s_tid=srchtitle

Note that the release date on those tools goes back to 2006, so long before this question was asked.