How to perform a complicated change of variables f

I have an integer polynomial in four variables (w, x, y, and z) that I know can be written as an integer polynomial in these six variables:

a = w z
b = x y
c = w^3 + z^3
d = x + y
e = w^3 x + y z^3
f = w^3 y + x z^3

How can I use Mathematica (or maybe Java) to easily do this change of variables?

Such rewriting can be done by forming a Groebner basis of the replacement polynomials, with respect to a variable order that favors using a-f over w-z. Then use PolynomialReduce with respect to the same order to rewrite your polynomial.

Here is an example. I'll start with replacement rules so I can construct a polynomial such that we know the expected result.

reprules = {a -> w*z, b -> x*y, c -> (w^3 + z^3), 
 d -> (x + y), e -> (w^3*x + y*z^3), f -> (w^3*y + x*z^3)};

Now recast as polynomial relations.

reppolys = Apply[Subtract, reprules, 1];

Here we create an example.

poly = 
 a^2*b + 3*b^2*c^3 - 2*d*e*f + 11*b*f^2 - 5 a*d^2*e /. reprules // Expand

Out[11]= -2*w^6*x^2*y - 2*w^6*x*y^2 + 3*w^9*x^2*y^2 + 11*w^6*x*y^3 - 
  5*w^4*x^3*z - 10*w^4*x^2*y*z - 5*w^4*x*y^2*z + w^2*x*y*z^2 - 2*w^3*x^3*z^3 - 
  2*w^3*x^2*y*z^3 - 2*w^3*x*y^2*z^3 + 22*w^3*x^2*y^2*z^3 + 9*w^6*x^2*y^2*z^3 - 
  2*w^3*y^3*z^3 - 5*w*x^2*y*z^4 - 10*w*x*y^2*z^4 - 5*w*y^3*z^4 -
  2*x^2*y*z^6 + 11*x^3*y*z^6 - 2*x*y^2*z^6 + 9*w^3*x^2*y^2*z^6 + 3*x^2*y^2*z^9

Form the Groebner basis mentioned above.

gb = GroebnerBasis[reppolys, {w, x, y, z, a, b, c, d, e, f}];

Use it to reduce our input to recover the expected result.

PolynomialReduce[poly, 
  gb, {w, x, y, z, a, b, c, d, e, f}][[2]]

Out[12]= a^2*b + 3*b^2*c^3 - 5*a*d^2*e - 2*d*e*f + 11*b*f^2

---edit---

A comment asks about descriptions of Groebner bases. For my own take on the Mathematica functionality, there is an elderly TMJ article. Can be found at

http://library.wolfram.com/infocenter/Articles/2179/

Among the better books related to this topic there is the UTM series text

Ideals, Varieties, and Algorithms by Cox, Lottle, and O'Shea.

An Introduction to Gröbner Bases by Adams and Loustaunau (AMS) is also quite good.

---end edit---

Daniel Lichtblau