I am seeking for an efficient algorithm to compute a multivariate polynomial of a fixed structure, but different coefficients and evaluation points. The question is the same as this one, which apparently did not draw much attention. I am working in MATLAB, so "efficient" probably in this situation means to vectorize as much as possible. Thank you.
Regards,
Ivan
Your question is answered in the paper
W.C. Rheinboldt, C.K. Mesztenyi and J.M. Fitzgerald,
On the evaluation of multivariate polynomials and their derivatives,
BIT 17 (1977), 437-450.
The paper contains pseudocode, but was written at a time where vectorization was not yet a common problem. But to simultaneously evaluate pol(coef,x) in Matlab for many values of (coef,x), you can apply the algorithm at is is with pointwise operations applied to vectors coef(i,:) and x(i,:). This vectorizes perfectly.
Which kind of multivariate polynomial? For what application (interpolation, curve fitting, computing derivatives...)? Structured Cartesian data points or scattered data? Do you require continuous derivatives? How many derivatives?
Without knowing this is hard to give you a "good" accurate answer. A general one would be:
For structured Cartesian data take a look at the matlab Spline Toolbox of deBoor. You can easily, and very efficiently compute tensor-product B-Splines for as many variables as you want, in as many dimensions as you want, and with as many continuous derivatives as you want (althoug you shouldnt use more than 15-20).
For multidimensional scattered data there are a couple of implementations of radial basis functions for matlab, a google search for "radial basis functions matlab" yields a couple of them.
Another possibility is to approximate your data using the Finite Element Toolbox (on an unstructured grid). This can be fast, however your derivatives might be discontinuous across elements.
Furthermore, matlab includes very fast implementations for a wide range of polynomial functions and is used frequently for approximation, interpolation and curve fitting so if you need an specific type of polynomial is very likely that someone has already implemented it. For example, a search for "Chebyshev polynomials matlab" yields also a lot of results.
