Polynomial rewriting question

[AndrewTamra]

Consider the following polynomials: Here x,y,z,w,h are variables; rest are constants.
(1) x*z-y*z, (2) x^2*w -2*x*y*w +y^2w + p, (3) 2*s+h+x-y

When we look closely at these, we notice that everywhere x and y occur, they occur as "x-y". Suppose we let t= x-y, then we can rewrite the above polynomials as (1) tz (2) t^2*w (3) 2*s+h+t.

How can do this in Mathematica? i.e., given the above 3 polynomials and the set of variables as input, I should get output of "x-y" and the 3 rewritten polynomials tz, t^2*w, 2*s+h+t.

Note that the above is an example. When I apply the program to any arbitrary and large number of polynomials, in place of "x-y" above, I would like to get the largest polynomial (maximum number of monomial terms) with as many variables in it as possible.

Thanks a lot.
Andrew.

[Leonid]

Hi Andrew,

One simple way is to substitute x= t+y and then call Simplify:

In[1] =
Clear[p1,p2,p3,x,y,z,w,p,h];
p1 = x*z - y*z;
p2 = x^2*w - 2*x*y*w + y^2 w + p;
p3 = 2*s + h + x - y;

In[2] = Simplify[# /. x -> t + y] & /@ {p1, p2, p3}

Out[2] = {t z,p+t^2 w,h+2 s+t}

Whether or not this will be useful in your setting I don't know -
depends on how complex is the real problem. For polynomials this
should
work.

Regards,
Leonid

[Daniel Lichtblau]

Leonid wrote:
> Hi Andrew,
>
> One simple way is to substitute x= t+y and then call Simplify:
>
> In[1] =
> Clear[p1,p2,p3,x,y,z,w,p,h];
> p1 = x*z - y*z;
> p2 = x^2*w - 2*x*y*w + y^2 w + p;
> p3 = 2*s + h + x - y;
>
> In[2] = Simplify[# /. x -> t + y] & /@ {p1, p2, p3}
>
> Out[2] = {t z,p+t^2 w,h+2 s+t}
>
> Whether or not this will be useful in your setting I don't know -
> depends on how complex is the real problem. For polynomials this
> should
> work.
>
> Regards,
> Leonid
>
>
> On Jul 2, 4:14 am, AndrewTamra <AndrewTa...@yahoo.com> wrote:

I somehow missed the original post (and cannot seem to locate it via the
MathGroup archives or Google groups, which might just be ineptness on my
part). Anyway, automating this process is hit-or-miss at best. Can be
attempted using FullSimplify and Experimental`OptimizeExpression, as below.

In[11]:= InputForm[Experimental`OptimizeExpression[
FullSimplify[{x*z-y*z, x^2*w -2*x*y*w +y^2w + p, 2*s+h+x-y}],
OptimizationLevel->2]]

Out[11]//InputForm=
Experimental`OptimizedExpression[Block[{Compile`$1, Compile`$2,
Compile`$4},
Compile`$1 = -y; Compile`$2 = x + Compile`$1; Compile`$4 = Compile`$2^2;
{Compile`$2*z, p + w*Compile`$4, h + 2*s + x + Compile`$1}]]

FullSimplify will (sometimes) manage to get its teeth into nature of the
x-y appearances e.g. in partial factorization, and then the expression
optimization might use this in common subexpression elimination.

Daniel Lichtblau
Wolfram Research

[AndrewTamra]

Thanks Daniel. You mentioned FullSimplify will SOMETIMES recognize the factorization. Could you think of any other deterministic method/algorithm I can implement in Mathematica for getting the simplification I am looking for?

Even a probablistic numeric algorithm is OK as well, where I can test within a reasonable probability, that there exists the factorization I am looking for; similar to the fast probablistic algorithms for Ideal membership problem. That way, first I can quickly determine the existence of such a simplification; then employ a slower (may be inefficient) algorithm to find the simplification (t=x-y in the example)

Thanks

[Daniel Lichtblau]

AndrewTamra wrote:
> Thanks Daniel. You mentioned FullSimplify will SOMETIMES recognize the
> factorization. Could you think of any other deterministic
method/algorithm
> I can implement in Mathematica for getting the simplification I am looking for?

Not offhand. The biggest impediment is in "factoring". I used the term
loosely, to mean ability to isolate x-y as a reasonable-to-use common
subexpression (CSE). I should have chosen a different term because
factoring, an algorithmic process, is quite well defined.

> Even a probablistic numeric algorithm is OK as well, where I can test within
> a reasonable probability, that there exists the factorization I am
looking
> for; similar to the fast probablistic algorithms for Ideal membership
problem.

Maybe I'm forgetting something important, but I'm not aware of fast
probabalistic ideal membership algorithms. Regardless, I do not know a
good way to deduce optimal CSEs, other than what you might find in CSE
elimination literature.

> That way, first I can quickly determine the existence of such a simplification;
> then employ a slower (may be inefficient) algorithm to find the simplification
> (t=x-y in the example)
>
> Thanks

I think finding the simplification is the crux of the problem. You won't
know one is there without explicitly finding it.

Daniel