Opened 11 years ago

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

Reported by: Owned by: steenpass Oleksandr major 3-1-4 and higher singular-kernel 3-1-3 std

Description

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
```

comment:1 Changed 11 years ago by 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.
1. "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?

comment:2 Changed 11 years ago by Oleksandr

Owner: changed from somebody to Oleksandr
Note: See TracTickets for help on using tickets.