Opened 11 years ago
Last modified 11 years ago
#375 new bug
std takes much longer for the same ideal, but with one more variable in the basering
Reported by: | steenpass | Owned by: | Oleksandr |
---|---|---|---|
Priority: | major | Milestone: | 3-1-4 and higher |
Component: | singular-kernel | Version: | 3-1-3 |
Keywords: | std | Cc: |
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
Change History (2)
comment:1 Changed 11 years ago by
comment:2 Changed 11 years ago by
Owner: | changed from somebody to Oleksandr |
---|
Note: See
TracTickets for help on using
tickets.
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:
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?