Bug #1640
MinSubsetOfGens does not find min subset
Description
Not sure what MinSubsetOfGens does, but it does not find a min card subset of the gens which generate the same ideal
use P ::= ZZ/(101)[x,y,z,t];
I := ideal([x^4*y*z +x^2*y^2*z^2 +z^6 +x^3*y^2 +y^3*z,
y^5*z +x^3*y^2 +x*z^4 +x^3*y +x*z^2]);
RGB := ReducedGBasis(I);
ideal(first(RGB,2)) = ideal(first(RGB,7)); --> true
M := MinSubsetOfGens(ideal(first(RGB,7))); -- be patient!
len(M) = 4; -- WRONG!
Related issues
History
#1
Updated by John Abbott over 2 years ago
Updated by I had wanted to show MinSubsetOfGens to my students, but maybe it is better not to do so.
The code is weird; I am not sure what it does.
#2
Updated by John Abbott over 2 years ago
I have now re-read the manual, and understood what it was trying to say.
Maybe re-write the manual entry to make it clearer?
#3
Updated by Anna Maria Bigatti over 2 years ago
Updated by - Description updated (diff)
#4
Updated by Anna Maria Bigatti over 2 years ago
John Abbott wrote:
I have now re-read the manual, and understood what it was trying to say.
Maybe re-write the manual entry to make it clearer?
Better like this?
NOTE: there no guarantee that <tt>S</tt> is the minimal subset with smallest cardinality.
#5
Updated by John Abbott over 2 years ago
- Related to Slug #1638: MinSubsetOfGens sometimes very slow added
#6
Updated by Anna Maria Bigatti over 2 years ago
During skype meeting, we implemented an improvement (discarding longest polynomial first). Now the given example is much faster (and returns the original 2 generators).
#7
Updated by Anna Maria Bigatti over 2 years ago
- Status changed from New to Feedback
- Assignee set to Anna Maria Bigatti
- % Done changed from 0 to 80
#8
Updated by John Abbott over 2 years ago
- % Done changed from 80 to 90
I did notice the following "phenomenon":
let RGB be a reduced GB ordered so that LTs are increasing (this is what CoCoA does anyway?)
- it was slow checking if first 2, first 3, first 4 etc gens produce the same ideal;
- it was quite fast to check if all-but-last, all-but-last-2, etc produce the same ideal.
We should test this before closing.
#9
Updated by John Abbott over 2 years ago
- Status changed from Feedback to Closed
- % Done changed from 90 to 100
- Estimated time set to 1.66 h
We had effectively already taken into account the comment 5 above.
Anna has just changed the code slightly to order by LT (previously ordered based on NumTerms).
Closing.