std takes much longer for the same ideal, but with one more variable in the basering

[steenpass]

In the following example, both std computations should be the same, but the second one takes much longer. The only difference is that the basering has one more variable.

> ring r = 0, (x,y), ds;
> poly f1 = 3x2+6xy+3y2+16x3+12x2y-6xy2-2y3+60x4-104x3y-42x2y2+36xy3-5y4-186x5-60x4y+184x3y2+24x2y3-30xy4+4y5+168x6+288x5y+30x4y2-120x3y3-18x2y4+12xy5-64x7-196x6y-192x5y2-40x4y3+32x3y4+12x2y5+9x8+40x7y+70x6y2+60x5y3+25x4y4+4x3y5;
> poly f2 = 3x2+6xy+3y2+4x3-6x2y-6xy2+4y3-26x4-28x3y+54x2y2-20xy3+5y4-12x5+92x4y+24x3y2-60x2y3+20xy4+48x6+12x5y-90x4y2-24x3y3+30x2y4-28x7-64x6y-24x5y2+32x4y3+20x3y4+5x8+20x7y+30x6y2+20x5y3+5x4y4;
> ideal i = f1, f2;
> int t = timer;
> ideal j = std(i);
> timer-t;
0
> ring s = 0, (x,y,z), ds;
> ideal i = fetch(r, i);
> t = timer;
> ideal j = std(i);   // aborted after several minutes

[levandov]

This can be healed by the method we were discussing with Hans back in 2004. Namely, assume that the object (ideal/module/matrix etc.) involves only a strict subset Y of basering variables X. Then one can determine this actual subset Y, change to the corresponding ring, compute over there and get back. Questions:

1. finding a subset Y is not too cheap: one has to analyze ALL exponent vectors in the worst case. Idea: look at the ordering and make the best out of it; this will work in the situation, close to elimination orderings.

2. "projecting" to the smaller ring in Y: here, one needs to construct the projected ordering for K[Y] from the given ordering on K[X].

In theory: thinking on a matrix for the ordering on K[X], remove the columns and rows, corr. to variables in X\Y. In practice: Hans has written some code for some situations we had in Plural; the drawback was as follows: from very effective internal encoding of orderings, the creation of an effective "projected" ordering is a complicated task. Have there been some progress in this direction?

2'. Getting back from the "projected" ring to the original is easy: monomials of the object are already correctly ordered, so no reordering is needed.

This ideology (of swapping to smaller rings when needed) can be theoretically built in any GB-connected computation (std, syz, lift etc.).

It would be very nice to estimate the cost of the operations 1 and 2... Ad 1: if an object does really involve all X, one checks this generically faster, than after looking at ALL monomials (earlier termination possible). As for the proof that Y is really complete, can there be an earlier termination?