6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ "which are more expensive than sums": I wouldn't be too conclusive about that. $\endgroup$ – Yves Daoust Sep 15 '15 at 9:43
  • $\begingroup$ A multiplication is more expensive than a sum for a computer, that's what I meant. Of course, the best way to define a "computationally efficient form" from a general point of view would be to assign weights $w_1$, $w_2$ for sums and multiplications resp. and to try to minimize $w_1*#sums + w_2*#mult$, but I've considered that would be a much more complicated problem and I've decided to simplify it a bit $\endgroup$ – Damaru Sep 15 '15 at 9:48
  • $\begingroup$ I don't agree with that. Floating-point additions can be slower than multiplications. $\endgroup$ – Yves Daoust Sep 15 '15 at 9:52
  • 1
    $\begingroup$ This seems to be a hard, open problem. The straightforward solution is to see the multivariate polynomial as a polynomial in one of the variables, and evaluate its coefficients by the same procedure, recursively. But there is no guarantee of optimality. $\endgroup$ – Yves Daoust Sep 15 '15 at 9:58
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.