Multivariate Horner scheme implementation in MATLAB

6 views (last 30 days)
Hello friends!
I have very long symbolic expressions (mainly polynomials or rational types) and I need to evaluate them many many times. Therefore,
in order to reduce the computational time I would like to re-write my expressions by their equivalent horner form. For instance, the expression
needs f=2*x^3-3*x^2+6*x-5 requires 8 multiplications and 3 additions while its following horner equivalent requires only 3 multiplications and 3 additions:
>> horner(f,x)
ans =
x*(x*(2*x - 3) + 6) - 5
Unfortunately, matlab only supports a univariate horner scheme. But, my expressions are multivariate and I need a multivariate Horner scheme
to simplify my long multivariate expressions. For instance, consider the following bi-variate expression:
syms x y
f = x^2+2*x*y+y^2;
If I go for a uni-variate Horner scheme then I get
>> horner(f,x)
ans =
x*(x + 2*y) + y^2
which requires less multiplications. This is, of course, an improvement. But, this is not the best improvement. A bi-variate Horner scheme
should give us (x+y)^2 as the best representation which needs only 2 arithmatics!
So, in sum, I need a matlab code which can implement a multivariate Horner scheme. I could find a python code but nothing in matlab. Unfortunately, I do not know python very well and really need a matlab code.
Any help is GREATLY appreciated!
Thanks in advance,
Babak
  7 Comments
Mohammad Shojaei Arani
Mohammad Shojaei Arani on 7 Mar 2022
Hi Torsten,
You are, most probably, right that perhaps there does not exit a perfect package to handle the problem of
finding a multivariate Horner scheme. It seems to me that a nuclear physics group in the Netherlands
called 'Nikhef' (see the link https://www.nikhef.nl/~form/) have programmed the best methods to tackle this problem.
Unfortunately, it is not written in matlab. In my opinion, it is essential to make a nice matlab multivariate Horner package as matlab is not very fast. Think of the expansion of an expression like (a+b+c)^30 which has many terms (of course matlab can handle this). If matlab wants to survive then such a package is really needed. Unfortunately, at this moment I am extremely busy with my research but whenever I find time I will try to make such a package. And, I hope that others will contribute to this.

Sign in to comment.

Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!