Computationally efficient form to evaluate multivariate polynomials?

Question

It is well known the Horner's method to transform a univariate polynomial into a computationally efficient form to evaluate it.

Instead of $\sum_{i=0}^na_ix^i$ you compute $(((a_nx+a_{n-1})x)+a_{n-2})\dots$ and the number of operations needed to evaluate the polynomial is reduced. Particularly, there are less multiplications (which are more expensive than sums)

My question is: Is there any method, algorithm to transform a multivariate polynomial into a computationally efficient form to evaluate it? Let's define the "computationally efficient form" as the one which requires the minimum multiplications

Answer 1

This is a very good and hard question. It is related to factoring filters in signal and image processing as the filter's $\mathcal{Z}$-transform are polynomials with as many variables as the filter has dimensions and that polynomial multiplication is equivalent to convolution of their coefficients.

Many people have thought about this before so it is kind of too large to give just one answer. Better to try and help give pointers to where to look.

I can drop some names which may help you find algorithms in the literature "Filter networks", "Fast transforms (FFT)", "Deconvolution" and even "Blind Deconvolution" could be helpful. Also if you want to dig into really advanced theory you can look at algebraic geometry, although I've heard it is quite a difficult field. Probably not something you would want to start out with.

Answer 2

Recursive Horner form is easy to implement and works well. Sort the terms of the expanded polynomial in descending lexicographical order, e.g. if x > y > z then terms are grouped first by powers of x, then by powers of y, then by powers of z. In one linear pass you can evaluate all the z's using Horner form to obtain a polynomial in {x,y} whose terms remain sorted. Then evaluate y using Horner form, finally evaluate x using Horner form. This should be fast enough even for very sparse polynomials.

If you're interested in the theoretical question, you can try Pippenger's algorithm. See https://cr.yp.to/papers/pippenger.pdf

Answer 3

There is no known algorithm for finding what you defined as "computationally efficient form" [1, Ch.2], except of course simply computing and comparing all possible factorisations. This method overall of course is not very "computationally efficient".

The best one can do is to use a clever heuristic to find "good" factorisations. I implemented a greedy heuristic similar to the one described in [1] in the Python package multivar_horner.

In this context one always has to balance the "investment" of computing a good factorisation of a multivariate polynomial with the benefits of having such a factorisation (cf. the speed tests of my package on Github).

Remark: Depending on the Hardware and Language in use it is actually not always best to just look for a factorisation with the minimal amount of multiplications. Exponentiation for example often is much more expensive than a multiplication. In the case of Python this does not seem to be the case (cf. how-is-exponentiation-implemented-in-python). These considerations affect the choice of "clever factorisation heuristic".

Here a pointer to papers on that subject (with different proposed heuristics):

[1] Greedy Algorithms for Optimizing Multivariate Horner Schemes, 2004

[2] On the multivariate Horner scheme,2000