Design #984
GroebnerFanIdeals: order matrices sometimes have "large" entries
Description
After using GroebnerFanIdeals
, I noticed that some order matrices can have quite "large" entries (e.g. greater than 1000).
Because of the way CoCoALib stores order vectors, having such large entries in the order matrix is potentially limiting (i.e. triggering problems of machine integer overflow if degrees become large).
Is it possible to produce order matrices with smaller entries?
Related issues
History
#1 Updated by John Abbott over 7 years ago
- Related to Support #973: GroebnerFanIdeals: verbosity and output style added
#2 Updated by John Abbott over 7 years ago
- Related to Support #977: "universal denominator" (related with GroebnerFanIdeals) added
#3 Updated by John Abbott over 7 years ago
Here is the same example as in issue #973
use P::=QQ[x,y,z]; I := ideal(x^5-3*y^3*z+x*y*z-2, y^3-2*z+5, z^2-12*x+7*y); GF := GroebnerFanIdeals(I); OrderMats := [OrdMat(RingOf(J)) | J in GF]; [M in OrderMats | max(flatten(GetRows(M))) > 1000]; --> two matrices
As far as I can tell the order of the ideals in GF
is the same from run to run, so I may refer to certain ideals just by specifying their indices. Anyway, I wanted to see which ideals corresponded to "lex" orderings: on my computer these have indices [36, 38, 94]
.
I had naively hoped to see that the matrices were just permutations of the identity matrix; instead they have larger entries:
>>> OrdMat(RingOf(GF[36])); matrix(ZZ, [[29, 30, 1], [842, 870, 0], [0, 0, -1]]) >>> OrdMat(RingOf(GF[38])); matrix(ZZ, [[6, 1, 4], [37, 0, 24], [0, 0, -1]]) >>> OrdMat(RingOf(GF[94])); matrix(ZZ, [[1, 29, 58], [0, 842, 1682], [0, 0, -1]])
Can something be done to make the matrix entries smaller?
For instance, it seems to me that the second row of the last matrix could be divided by 2 without affecting the ordering; similarly for second row of first matrix.
#4 Updated by John Abbott over 7 years ago
I noticed that in this example the order matrices always have strictly positive entries in the first row. Are zeroes not allowed?
It seems that GFan usually produces the first two rows, and then the last row is just [0,0,-1]
with the sole exception of the very first ideal whose order matrix corresponds to StdDegRevLex
.
One option could be to determine the "best" order matrix for each ideal once the supports of its reduced G-basis elements have been computed. This appears to be an integer linear programming problem.
#5 Updated by John Abbott about 7 years ago
- Related to Bug #1069: GroebnerFan: ERROR: Matrix must be invertible added
#6 Updated by John Abbott over 2 years ago
It seems that the first two rows are "almost parallel" -- why should that be?
Anyway, it should be easy to reduce the size of entries in row 2.
#7 Updated by John Abbott over 2 years ago
- Related to Bug #1634: Unexpected or unhelpful error using GroebnerFanIdeals added
#8 Updated by John Abbott 4 months ago
- Related to Slug #1049: GroebnerFan: slow examples added
#9 Updated by John Abbott 4 months ago
- Related to Bug #1371: French students' example with GFan added
#10 Updated by John Abbott 13 days ago
- Status changed from New to In Progress
Here are some examples I computed a while ago -- don't remember when, but I found the file recently.
// Info is: [biggest-ordmat-entry, ideal, size-of-gfan] // Best I found in deg=3 // [4930, ideal(y^3 +z^3, x^2*t +t^3, z*t^2 +t, x^3 +y*z^2), 1686] // deg=4 // [315375, ideal(t^4 +x^2*t, y^4 +x^2*t, x^4 +z, z^4 +x*y*t), 405] // [346712, ideal(t^4 +x^2*t, y^4 +x^2*t, x^4 +z, z^4 +x*t), 158] // [454314, ideal(y^4 +x^2*t, x^4 +z, z^4 +x*t, x^3*y +t^4), 1048] // [486180, ideal(y^4 +x^2*t, x^4 +z, z^4 +x*t, t^4 +y*z^2), 591] // [497042, ideal(y^4 +x^2*t, x^4 +z, z^4 +x*t, t^4 +y^2), 237] // [582332, ideal(y^4 +x^2*t, x^4 +z, z^4 +x*t, t^4 +y), 237]
#11 Updated by John Abbott 13 days ago
- Related to Feature #780: GroebnerFan/ExternalLib-GFan: improve package added