Multivariate Horner scheme implementation in MATLAB

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

[Torsten]

Use "matlabFunction" to convert your long expressions into function handles.

This will save much more time than using a horner scheme for evaluation.

[Mohammad Shojaei Arani]

Well, I have already done this. But, the computations are still expensive.

I have noticed, indirectly, that the commands 'simplify', 'simplifyFraction', etc cannot help to shorten my expressions. However,

the horner scheme is quite nice. But, then I need a mutivariate horner representation of my expressions.

I am surprised how such a code exists in python (which is free) but matlab does not have it!!!

[Mohammad Shojaei Arani]

I forgot to add that:

1) For sure, function handle is faster for evaluating expressions compared with using commands like 'subs'.

2) What I do is to : first, convert my symbolic expressions into a proper horner representation and second, apply the

command 'matlabFunction' to this horner representation (not the original symbolic expression)

[John D'Errico]

Your claim of a "bivariate" horner method on that example is simply the result of factoring the polynomial.

syms x y
f = x^2+2*x*y+y^2;
prod(factor(f))

ans = 

Anyway, Torsten is abolutely correct. You do not want to use symbolic polynomials IF you care about efficiency. Convert them to functions in MATLAB, that can be evaluated using double precision arithmetic. This will be far more efficient then any symbolic imporvements could possibly yield.

[Mohammad Shojaei Arani]

John!

I am a mathematician and know that (x+y)^2=x^2+2x*y+y^2. You should have read my message more

carefully. I mentioned that my expressions are extremely (=EXTREMELY) long. The case of (x+y)^2=x^2+2x*y+y^2

was just a simple example to explain to you my problem.

Again and again : I know that function handle is much faster than symbolic expressions evaluated by the command

'subs'. Right. But, since my symbolic expressions are extremely long it still takes a long time to do the calculations

using function handle.

Wht needs to be done is to 1) Convert the polynomials into a Horner form (which we know that its computing time

is minimal) and 2) Apply the 'matlabFunction' to 1.

For a uni-variate polynomial we know that:

The computational time for a Horner representation of a polynomial is optimal : For a univariate polynomial of degree n, the Horner scheme requires only n multiplications and n additions,althogether 2n arithmatic calculations. Any other representation demands more than 2n arithmatics.

[Torsten]

A multivariate Horner scheme under MATLAB does not exist.

And the package under Python also will not be useful for your purpose because it can only handle very basic cases. But you have unstructured and very long expressions as you wrote.

So I think you will have to be satisfied with what MATLAB can offer, namely "matlabFunction". Or you can completely restructure your code to numerical, not symbolic computation (which I would recommend).

[Mohammad Shojaei Arani]

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.