We will work with the following example, the cone over a product of an elliptic curve and a genus 3 planar curve, embedded with a Segre embedding, so the cone over a surface, embedded in $P^8$ (defined by 31 equations). The Jacobian is a relatively sparse $9 \times 31$ matrix and to compute the full Jacobian ideal we would need to compute the 61,847,604 minors of size $6 \times 6$.
i1 : S = ZZ/103[x_1..x_9]; |
i2 : J = ideal(x_6*x_8-x_5*x_9,x_3*x_8-x_2*x_9,x_6*x_7-x_4*x_9,x_5*x_7-x_4*x_8,x_3*x_7-x_1*x_9,x_2*x_7-x_1*x_8,x_3*x_5-x_2*x_6,x_3*x_4-x_1*x_6,x_2*x_4-x_1*x_5,x_7^3-x_8^2*x_9-x_7*x_9^2,x_4*x_7^2-x_5*x_8*x_9-x_4*x_9^2, x_1*x_7^2-x_2*x_8*x_9-x_1*x_9^2,x_4^2*x_7-x_5^2*x_9-x_4*x_6*x_9,x_1*x_4*x_7-x_2*x_5*x_9-x_1*x_6*x_9,x_1^2*x_7-x_2^2*x_9-x_1*x_3*x_9,x_4^3-x_5^2*x_6-x_4*x_6^2,x_1*x_4^2-x_2*x_5*x_6-x_1*x_6^2,x_1^2*x_4-x_2^2*x_6-x_1*x_3*x_6,x_1^3-x_2^2*x_3-x_1*x_3^2,x_3^4+x_6^4-x_9^4,x_2*x_3^3+x_5*x_6^3-x_8*x_9^3,x_1*x_3^3+x_4*x_6^3-x_7*x_9^3,x_2^2*x_3^2+x_5^2*x_6^2-x_8^2*x_9^2,x_1*x_2*x_3^2+x_4*x_5*x_6^2-x_7*x_8*x_9^2,x_1^2*x_3^2+x_4^2*x_6^2-x_7^2*x_9^2,x_2^3*x_3+x_5^3*x_6-x_8^3*x_9,x_1*x_2^2*x_3+x_4*x_5^2*x_6-x_7*x_8^2*x_9,x_1^2*x_2*x_3+x_4^2*x_5*x_6-x_7^2*x_8*x_9,x_2^4+x_5^4-x_8^4,x_1*x_2^3+x_4*x_5^3-x_7*x_8^3,x_1^2*x_2^2+x_4^2*x_5^2-x_7^2*x_8^2)
o2 = ideal (x x - x x , x x - x x , x x - x x , x x - x x , x x - x x ,
6 8 5 9 3 8 2 9 6 7 4 9 5 7 4 8 3 7 1 9
------------------------------------------------------------------------
3 2 2
x x - x x , x x - x x , x x - x x , x x - x x , x - x x - x x ,
2 7 1 8 3 5 2 6 3 4 1 6 2 4 1 5 7 8 9 7 9
------------------------------------------------------------------------
2 2 2 2 2 2
x x - x x x - x x , x x - x x x - x x , x x - x x - x x x , x x x
4 7 5 8 9 4 9 1 7 2 8 9 1 9 4 7 5 9 4 6 9 1 4 7
------------------------------------------------------------------------
2 2 3 2 2 2
- x x x - x x x , x x - x x - x x x , x - x x - x x , x x - x x x
2 5 9 1 6 9 1 7 2 9 1 3 9 4 5 6 4 6 1 4 2 5 6
------------------------------------------------------------------------
2 2 2 3 2 2 4 4 4 3
- x x , x x - x x - x x x , x - x x - x x , x + x - x , x x +
1 6 1 4 2 6 1 3 6 1 2 3 1 3 3 6 9 2 3
------------------------------------------------------------------------
3 3 3 3 3 2 2 2 2 2 2 2 2
x x - x x , x x + x x - x x , x x + x x - x x , x x x + x x x -
5 6 8 9 1 3 4 6 7 9 2 3 5 6 8 9 1 2 3 4 5 6
------------------------------------------------------------------------
2 2 2 2 2 2 2 3 3 3 2 2
x x x , x x + x x - x x , x x + x x - x x , x x x + x x x -
7 8 9 1 3 4 6 7 9 2 3 5 6 8 9 1 2 3 4 5 6
------------------------------------------------------------------------
2 2 2 2 4 4 4 3 3 3 2 2
x x x , x x x + x x x - x x x , x + x - x , x x + x x - x x , x x
7 8 9 1 2 3 4 5 6 7 8 9 2 5 8 1 2 4 5 7 8 1 2
------------------------------------------------------------------------
2 2 2 2
+ x x - x x )
4 5 7 8
o2 : Ideal of S
|
i3 : M = jacobian J
o3 = {1} | 0 0 0 0 -x_9 -x_8 0 -x_6 -x_5 0
{1} | 0 -x_9 0 0 0 x_7 -x_6 0 x_4 0
{1} | 0 x_8 0 0 x_7 0 x_5 x_4 0 0
{1} | 0 0 -x_9 -x_8 0 0 0 x_3 x_2 0
{1} | -x_9 0 0 x_7 0 0 x_3 0 -x_1 0
{1} | x_8 0 x_7 0 0 0 -x_2 -x_1 0 0
{1} | 0 0 x_6 x_5 x_3 x_2 0 0 0 3x_7^2-x_9^2
{1} | x_6 x_3 0 -x_4 0 -x_1 0 0 0 -2x_8x_9
{1} | -x_5 -x_2 -x_4 0 -x_1 0 0 0 0 -x_8^2-2x_7x_9
------------------------------------------------------------------------
0 x_7^2-x_9^2 0 x_4x_7-x_6x_9
0 -x_8x_9 0 -x_5x_9
0 0 0 0
x_7^2-x_9^2 0 2x_4x_7-x_6x_9 x_1x_7
-x_8x_9 0 -2x_5x_9 -x_2x_9
0 0 -x_4x_9 -x_1x_9
2x_4x_7 2x_1x_7 x_4^2 x_1x_4
-x_5x_9 -x_2x_9 0 0
-x_5x_8-2x_4x_9 -x_2x_8-2x_1x_9 -x_5^2-x_4x_6 -x_2x_5-x_1x_6
------------------------------------------------------------------------
2x_1x_7-x_3x_9 0 x_4^2-x_6^2 2x_1x_4-x_3x_6
-2x_2x_9 0 -x_5x_6 -2x_2x_6
-x_1x_9 0 0 -x_1x_6
0 3x_4^2-x_6^2 2x_1x_4 x_1^2
0 -2x_5x_6 -x_2x_6 0
0 -x_5^2-2x_4x_6 -x_2x_5-2x_1x_6 -x_2^2-x_1x_3
x_1^2 0 0 0
0 0 0 0
-x_2^2-x_1x_3 0 0 0
------------------------------------------------------------------------
3x_1^2-x_3^2 0 0 x_3^3 0 x_2x_3^2
-2x_2x_3 0 x_3^3 0 2x_2x_3^2 x_1x_3^2
-x_2^2-2x_1x_3 4x_3^3 3x_2x_3^2 3x_1x_3^2 2x_2^2x_3 2x_1x_2x_3
0 0 0 x_6^3 0 x_5x_6^2
0 0 x_6^3 0 2x_5x_6^2 x_4x_6^2
0 4x_6^3 3x_5x_6^2 3x_4x_6^2 2x_5^2x_6 2x_4x_5x_6
0 0 0 -x_9^3 0 -x_8x_9^2
0 0 -x_9^3 0 -2x_8x_9^2 -x_7x_9^2
0 -4x_9^3 -3x_8x_9^2 -3x_7x_9^2 -2x_8^2x_9 -2x_7x_8x_9
------------------------------------------------------------------------
2x_1x_3^2 0 x_2^2x_3 2x_1x_2x_3 0 x_2^3
0 3x_2^2x_3 2x_1x_2x_3 x_1^2x_3 4x_2^3 3x_1x_2^2
2x_1^2x_3 x_2^3 x_1x_2^2 x_1^2x_2 0 0
2x_4x_6^2 0 x_5^2x_6 2x_4x_5x_6 0 x_5^3
0 3x_5^2x_6 2x_4x_5x_6 x_4^2x_6 4x_5^3 3x_4x_5^2
2x_4^2x_6 x_5^3 x_4x_5^2 x_4^2x_5 0 0
-2x_7x_9^2 0 -x_8^2x_9 -2x_7x_8x_9 0 -x_8^3
0 -3x_8^2x_9 -2x_7x_8x_9 -x_7^2x_9 -4x_8^3 -3x_7x_8^2
-2x_7^2x_9 -x_8^3 -x_7x_8^2 -x_7^2x_8 0 0
------------------------------------------------------------------------
2x_1x_2^2 |
2x_1^2x_2 |
0 |
2x_4x_5^2 |
2x_4^2x_5 |
0 |
-2x_7x_8^2 |
-2x_7^2x_8 |
0 |
9 31
o3 : Matrix S <--- S
|
getSubmatrixOfRank: We begin by exploring submatrices of this matrix, chosen using different strategies. We try to select submatrices of rank 6 with the command getSubmatrixOfRank. The Random strategy for instance selects a smallest matrix. On the other hand, GRevLexSmallest (respectively GRevLexLargest) tries to choose a matrix with minimal (respectively maximal) values with respect to a random GRevLex order. LexSmallest and LexLargest selects a smallest submatrix whose terms have smallest and largest value with respect to a random Lex monomial order. Points first finds a point on $V(J)$ and then finds a submatrix where the matrix has full rank after being evaluated at that point. For more details on how these strategies work, see getSubmatrixOfRank(...,Strategy=>...).
i4 : a = getSubmatrixOfRank(6, M**(S/J), Strategy=>Random)
o4 = {{0, 4, 5, 6, 7, 8}, {24, 8, 13, 5, 1, 25}}
o4 : List
|
i5 : M^(a#0)_(a#1)
o5 = {1} | 2x_1x_3^2 -x_5 x_4x_7-x_6x_9 -x_8 0 0 |
{1} | 0 -x_1 -x_2x_9 0 0 3x_5^2x_6 |
{1} | 2x_4^2x_6 0 -x_1x_9 0 0 x_5^3 |
{1} | -2x_7x_9^2 0 x_1x_4 x_2 0 0 |
{1} | 0 0 0 -x_1 x_3 -3x_8^2x_9 |
{1} | -2x_7^2x_9 0 -x_2x_5-x_1x_6 0 -x_2 -x_8^3 |
6 6
o5 : Matrix S <--- S
|
i6 : d = getSubmatrixOfRank(6, M**(S/J), MaxMinors=>100, Strategy=>LexSmallest)
o6 = {{8, 7, 1, 2, 6, 4}, {2, 3, 8, 7, 12, 30}}
o6 : List
|
i7 : M^(d#0)_(d#1)
o7 = {1} | -x_4 0 0 0 -x_5^2-x_4x_6 0 |
{1} | 0 -x_4 0 0 0 -2x_7^2x_8 |
{1} | 0 0 x_4 0 0 2x_1^2x_2 |
{1} | 0 0 0 x_4 0 0 |
{1} | x_6 x_5 0 0 x_4^2 -2x_7x_8^2 |
{1} | 0 x_7 -x_1 0 -2x_5x_9 2x_4^2x_5 |
6 6
o7 : Matrix S <--- S
|
i8 : e = getSubmatrixOfRank(6, M**(S/J), Strategy=>LexSmallestTerm)
o8 = {{6, 3, 7, 4, 0, 2}, {4, 7, 1, 6, 18, 19}}
o8 : List
|
i9 : M^(e#0)_(e#1)
o9 = {1} | x_3 0 0 0 0 0 |
{1} | 0 x_3 0 0 0 0 |
{1} | 0 0 x_3 0 0 0 |
{1} | 0 0 0 x_3 0 0 |
{1} | -x_9 -x_6 0 0 3x_1^2-x_3^2 0 |
{1} | x_7 x_4 x_8 x_5 -x_2^2-2x_1x_3 4x_3^3 |
6 6
o9 : Matrix S <--- S
|
i10 : f = getSubmatrixOfRank(6, M**(S/J), MaxMinors=>100, Strategy=>LexLargest)
o10 = {{0, 2, 1, 5, 8, 4}, {29, 25, 28, 17, 14, 16}}
o10 : List
|
i11 : M^(f#0)_(f#1)
o11 = {1} | x_2^3 0 0 2x_1x_4-x_3x_6 2x_1x_7-x_3x_9
{1} | 0 x_2^3 0 -x_1x_6 -x_1x_9
{1} | 3x_1x_2^2 3x_2^2x_3 4x_2^3 -2x_2x_6 -2x_2x_9
{1} | 0 x_5^3 0 -x_2^2-x_1x_3 0
{1} | 0 -x_8^3 0 0 -x_2^2-x_1x_3
{1} | 3x_4x_5^2 3x_5^2x_6 4x_5^3 0 0
-----------------------------------------------------------------------
x_4^2-x_6^2 |
0 |
-x_5x_6 |
-x_2x_5-2x_1x_6 |
0 |
-x_2x_6 |
6 6
o11 : Matrix S <--- S
|
i12 : g = getSubmatrixOfRank(6, M**(S/J), Strategy=>Points)
o12 = {{0, 1, 2, 3, 4, 6}, {0, 1, 2, 4, 9, 19}}
o12 : List
|
i13 : M^(g#0)_(g#1)
o13 = {1} | 0 0 0 -x_9 0 0 |
{1} | 0 -x_9 0 0 0 0 |
{1} | 0 x_8 0 x_7 0 4x_3^3 |
{1} | 0 0 -x_9 0 0 0 |
{1} | -x_9 0 0 0 0 0 |
{1} | 0 0 x_6 x_3 3x_7^2-x_9^2 0 |
6 6
o13 : Matrix S <--- S
|
You can see that different strategies typically produce submatrices which can appear quite different in their complexity. We left off the strategies GRevLexLargest, GRevLexSmallest, GRevLexSmallestTerm as they behave very poorly on this example (indeed, we had to increase MaxMinors, the number of submatrices considered, for both LexSmallest and LexLargest as they did not find a submatrix in the default number of attempts). Of course, one can view the matrix over $S$, instead of $S/J$, where it's easier to choose a submatrix.
i14 : b = getSubmatrixOfRank(6, M, Strategy=>GRevLexSmallest)
o14 = {{4, 7, 3, 6, 8, 1}, {6, 1, 7, 4, 2, 8}}
o14 : List
|
i15 : M^(b#0)_(b#1)
o15 = {1} | x_3 0 0 0 0 -x_1 |
{1} | 0 x_3 0 0 0 0 |
{1} | 0 0 x_3 0 -x_9 x_2 |
{1} | 0 0 0 x_3 x_6 0 |
{1} | 0 -x_2 0 -x_1 -x_4 0 |
{1} | -x_6 -x_9 0 0 0 x_4 |
6 6
o15 : Matrix S <--- S
|
i16 : c = getSubmatrixOfRank(6, M, Strategy=>GRevLexSmallestTerm)
o16 = {{1, 0, 7, 6, 4, 2}, {6, 7, 0, 2, 3, 4}}
o16 : List
|
i17 : M^(c#0)_(c#1)
o17 = {1} | -x_6 0 0 0 0 0 |
{1} | 0 -x_6 0 0 0 -x_9 |
{1} | 0 0 x_6 0 -x_4 0 |
{1} | 0 0 0 x_6 x_5 x_3 |
{1} | x_3 0 -x_9 0 x_7 0 |
{1} | x_5 x_4 0 0 0 x_7 |
6 6
o17 : Matrix S <--- S
|
i18 : h = getSubmatrixOfRank(6, M, Strategy=>LexLargest)
o18 = {{7, 8, 3, 0, 6, 4}, {30, 27, 10, 11, 9, 3}}
o18 : List
|
i19 : M^(h#0)_(h#1)
o19 = {1} | -2x_7^2x_8 -x_7^2x_9 -x_5x_9 -x_2x_9
{1} | 0 -x_7^2x_8 -x_5x_8-2x_4x_9 -x_2x_8-2x_1x_9
{1} | 2x_4x_5^2 2x_4x_5x_6 x_7^2-x_9^2 0
{1} | 2x_1x_2^2 2x_1x_2x_3 0 x_7^2-x_9^2
{1} | -2x_7x_8^2 -2x_7x_8x_9 2x_4x_7 2x_1x_7
{1} | 2x_4^2x_5 x_4^2x_6 -x_8x_9 0
-----------------------------------------------------------------------
-2x_8x_9 -x_4 |
-x_8^2-2x_7x_9 0 |
0 -x_8 |
0 0 |
3x_7^2-x_9^2 x_5 |
0 x_7 |
6 6
o19 : Matrix S <--- S
|
chooseGoodMinors: In many cases, we want to consider the determinant of the submatrices we just found, perhaps to append the determinant to an ideal. The function chooseGoodMinors helps us do that. Note that chooseGoodMinors does not check that the submatrix we are computing has full rank (except by computing its determinant and adding it to our working ideal).
i20 : chooseGoodMinors(1, 6, M, J, Strategy=>Random)
5 4 3 2 3 5 3 3 6 3 3 3 2 2 3
o20 = ideal(16x x x x x + 32x x x x x + 16x x x x x - 16x x x x x x -
1 2 3 4 7 1 2 3 4 7 1 2 3 4 7 2 3 4 5 6 7
-----------------------------------------------------------------------
4 2 2 3 5 4 3 3 2 4 3 2 4 4 2
16x x x x x x x + 16x x x x x - 16x x x x x x - 32x x x x x x -
1 2 3 4 5 6 7 1 2 4 6 7 1 2 3 4 6 7 1 2 3 4 7 8
-----------------------------------------------------------------------
3 2 5 2 3 3 4 2 4 5 2 2 3 2 2 2
32x x x x x x + 24x x x x x x + 24x x x x x x + 32x x x x x x x x -
1 2 3 4 7 8 1 2 3 5 7 8 1 2 3 5 7 8 1 2 3 4 5 6 7 8
-----------------------------------------------------------------------
2 3 3 2 2 4 4 2 3 2 4 2 3 3 4 2
24x x x x x x x x - 32x x x x x x + 32x x x x x x x + 24x x x x x x
1 2 3 4 5 6 7 8 1 2 4 6 7 8 1 2 3 4 6 7 8 1 2 5 6 7 8
-----------------------------------------------------------------------
4 4 2 3 3 4 2 4 5 2
- 24x x x x x x x - 16x x x x x x - 16x x x x x x +
1 2 3 5 6 7 8 1 2 3 4 7 9 1 2 3 4 7 9
-----------------------------------------------------------------------
2 3 2 2 2 3 3 4 2 4 4 2 6 4
16x x x x x x x x - 16x x x x x x + 16x x x x x x x - 8x x x x x x
1 2 3 4 5 6 7 9 1 2 4 6 7 9 1 2 3 4 6 7 9 2 3 4 7 8 9
-----------------------------------------------------------------------
4 5 2 2 6 5 4
+ 16x x x x x x x + 24x x x x x x x + 16x x x x x x x -
1 2 3 4 7 8 9 1 2 3 4 7 8 9 1 2 3 5 7 8 9
-----------------------------------------------------------------------
3 6 2 3 3 2 2 4 3 2
16x x x x x x x - 16x x x x x x x x + 16x x x x x x x +
1 2 3 5 7 8 9 1 2 3 4 5 7 8 9 1 3 4 5 7 8 9
-----------------------------------------------------------------------
2 3 2 3 2 4 2 2 5 2 2
32x x x x x x x x - 8x x x x x x x x - 8x x x x x x x x +
1 2 3 4 5 7 8 9 2 3 4 5 6 7 8 9 1 3 4 5 6 7 8 9
-----------------------------------------------------------------------
2 4 2 3 3 2 2 3 3 3 3
16x x x x x x x - 48x x x x x x x x - 32x x x x x x x x +
1 2 4 6 7 8 9 1 2 3 4 6 7 8 9 1 2 4 5 6 7 8 9
-----------------------------------------------------------------------
4 3 2 4 4 2 3 2 5 2 3 3 2 3 2
32x x x x x x x x x - 4x x x x x x - 4x x x x x x - 8x x x x x x +
1 2 3 4 5 6 7 8 9 1 2 3 5 8 9 1 2 3 5 8 9 1 3 4 5 8 9
-----------------------------------------------------------------------
2 4 3 2 4 2 3 2 3 3 4 2 4 4 2
4x x x x x x x + 8x x x x x x x + 16x x x x x x + 16x x x x x x x -
1 3 4 5 6 8 9 1 2 4 5 6 8 9 2 3 4 7 8 9 1 2 3 4 7 8 9
-----------------------------------------------------------------------
2 3 3 3 2 4 3 3 2 4 3 3 5 4 2
16x x x x x x x - 16x x x x x x + 16x x x x x x - 16x x x x x x -
1 2 3 4 7 8 9 1 3 4 7 8 9 1 4 6 7 8 9 1 2 3 4 7 9
-----------------------------------------------------------------------
2 3 5 2 3 6 2 3 3 2 2 2 4 2 2 2
32x x x x x x - 16x x x x x x + 16x x x x x x x + 16x x x x x x x x
1 2 3 4 7 9 1 2 3 4 7 9 2 3 4 5 6 7 9 1 2 3 4 5 6 7 9
-----------------------------------------------------------------------
5 4 2 3 2 4 2 2 4 4 2 3 2 5 2
- 16x x x x x x + 16x x x x x x x - 8x x x x x x - 8x x x x x x +
1 2 4 6 7 9 1 2 3 4 6 7 9 1 2 3 4 8 9 1 2 3 4 8 9
-----------------------------------------------------------------------
3 3 4 2 4 5 2 3 3 3 2 2 2 4 2 2 2
8x x x x x x + 8x x x x x x - 16x x x x x x + 8x x x x x x x -
1 2 3 5 8 9 1 2 3 5 8 9 1 3 4 5 8 9 1 3 4 5 6 8 9
-----------------------------------------------------------------------
2 3 3 2 4 2 2 3 2 3 3 4 2 4 4 2
8x x x x x x x x + 16x x x x x x + 8x x x x x x - 8x x x x x x x +
1 2 3 4 5 6 8 9 1 2 4 6 8 9 1 2 5 6 8 9 1 2 3 5 6 8 9
-----------------------------------------------------------------------
2 4 2 3 2 5 2 3 2 3 3 2 3 2 4 2 3 2
8x x x x x x + 8x x x x x x + 8x x x x x x + 8x x x x x x x -
2 3 4 7 8 9 1 3 4 7 8 9 2 3 5 7 8 9 1 2 3 5 7 8 9
-----------------------------------------------------------------------
2 2 3 2 3 2 2 3 4 2 2 4 4 2 2 4 4 2
16x x x x x x - 8x x x x x x x - 8x x x x x x + 8x x x x x x +
1 4 6 7 8 9 1 2 3 5 7 8 9 1 3 5 7 8 9 1 5 6 7 8 9
-----------------------------------------------------------------------
3 3 4 3 4 5 3 2 3 2 2 3 3 3 4 3
16x x x x x + 16x x x x x - 16x x x x x x x + 16x x x x x -
1 2 3 4 9 1 2 3 4 9 1 2 3 4 5 6 9 1 2 4 6 9
-----------------------------------------------------------------------
4 4 3 2 3 3 3 2 4 3 3 2 4 3 3
16x x x x x x - 16x x x x x x x - 16x x x x x x + 16x x x x x x +
1 2 3 4 6 9 1 2 3 4 7 8 9 1 3 4 7 8 9 1 4 6 7 8 9
-----------------------------------------------------------------------
2 4 4 3 5 4 3 2 3 4 3 5 3 4
4x x x x x + 4x x x x x - 8x x x x x x - 16x x x x x +
2 3 5 8 9 1 3 5 8 9 1 4 5 6 8 9 1 2 4 7 9
-----------------------------------------------------------------------
3 2 3 4 2 4 2 4 3 2 2 4 2 2 2 2 4
16x x x x x x + 16x x x x x x + 16x x x x x x x - 16x x x x x x x +
1 2 3 4 7 9 1 2 4 7 8 9 1 2 3 4 7 8 9 1 4 5 6 7 8 9
-----------------------------------------------------------------------
2 4 3 4 5 3 4 3 3 3 4 4 3 4 2 2 3 3 4
8x x x x x + 8x x x x x - 8x x x x x - 8x x x x x x - 16x x x x x
2 3 4 8 9 1 3 4 8 9 2 3 5 8 9 1 2 3 5 8 9 1 4 6 8 9
-----------------------------------------------------------------------
2 3 2 5 3 3 2 5 4 2 5 5 6
+ 16x x x x x x - 16x x x x x - 16x x x x x x + 16x x x x x -
1 4 5 7 8 9 2 3 4 8 9 1 2 3 4 8 9 1 2 4 7 9
-----------------------------------------------------------------------
3 2 6
16x x x x x x )
1 2 3 4 7 9
o20 : Ideal of S
|
i21 : chooseGoodMinors(1, 6, M, J, Strategy=>LexSmallest)
6 5 3 2 2 3 4 2 3 2
o21 = ideal(- x x + x x x + x x x x - x x x x + x x x - x x x x )
2 4 1 4 5 2 4 5 6 1 4 5 6 2 4 6 1 4 5 6
o21 : Ideal of S
|
i22 : chooseGoodMinors(1, 6, M, J, Strategy=>LexSmallestTerm)
8 5 2 6 2 3 2 3 4 4
o22 = ideal(3x - 3x x x - 4x x + x x x + x x )
7 7 8 9 7 9 7 8 9 7 9
o22 : Ideal of S
|
i23 : chooseGoodMinors(1, 6, M, J, Strategy=>LexLargest)
3 2 9 4 10 4 10 2 11 2 12 2 7 2 2
o23 = ideal(- 4x x x - 4x x + 4x x + 8x x x + 4x x + 24x x x x x +
1 2 3 1 3 2 3 1 2 3 1 3 1 2 3 4 6
-----------------------------------------------------------------------
2 8 2 2 2 2 6 3 3 7 3 2 8 3 9 3
24x x x x - 8x x x x x - 8x x x x - 12x x x x - 12x x x x -
1 3 4 6 1 2 3 4 6 1 3 4 6 2 3 4 6 1 3 4 6
-----------------------------------------------------------------------
3 7 3 8 3 3 2 5 4 4 6 4 4 6 4
24x x x x - 24x x x x x - 12x x x x - 12x x x + 28x x x +
2 3 5 6 1 2 3 5 6 1 2 3 6 1 3 6 2 3 6
-----------------------------------------------------------------------
2 7 4 2 8 4 2 3 2 6 2 4 2 6 2 4 7 5 7
36x x x x + 8x x x + 8x x x x x + 8x x x x - 4x x x x - 4x x x x
1 2 3 6 1 3 6 1 2 3 4 6 1 3 4 6 2 3 4 6 1 3 4 6
-----------------------------------------------------------------------
3 3 7 4 7 4 2 8 2 3 8 2 4 8
- 24x x x x - 24x x x x x + 24x x x + 20x x x x - 4x x x +
2 3 5 6 1 2 3 5 6 2 3 6 1 2 3 6 1 3 6
-----------------------------------------------------------------------
4 6 2 2 2 7 2 2 2 8 2 2 3 3 3 2 2
24x x x x - 24x x x x x - 24x x x x + 24x x x x x x +
1 3 7 9 1 2 3 7 9 1 3 7 9 1 3 4 6 7 9
-----------------------------------------------------------------------
4 3 2 2 2 3 4 2 2 2 4 4 2 2 4 3 2
41x x x x x x x - 41x x x x x x + 24x x x x x - 41x x x x x x x x -
1 2 3 5 6 7 9 1 2 3 6 7 9 1 3 6 7 9 1 2 3 4 6 7 8 9
-----------------------------------------------------------------------
2 3 4 2 7 2 5 5 3 2 2 6 3
7x x x x x x x - 48x x x x x x x - 24x x x x + 24x x x x x +
1 2 3 6 7 8 9 1 2 4 6 7 8 9 1 3 7 9 1 2 3 7 9
-----------------------------------------------------------------------
3 7 3 2 8 3 9 3 3 3 2 2 3
12x x x x + 12x x x x + 12x x x x - 24x x x x x x -
1 3 7 9 2 3 7 9 1 3 7 9 1 3 4 6 7 9
-----------------------------------------------------------------------
4 2 3 2 3 3 3 2 4 3 3
41x x x x x x x x - 29x x x x x x x + 35x x x x x x -
1 2 3 4 5 6 7 9 1 2 3 4 6 7 9 1 3 4 6 7 9
-----------------------------------------------------------------------
2 3 3 3 2 2 2 4 3 3 3 4 3 6 3
10x x x x x x x + 17x x x x x x - 20x x x x x + 48x x x x x x x -
1 2 3 5 6 7 9 1 2 3 6 7 9 1 3 6 7 9 1 2 4 5 6 7 9
-----------------------------------------------------------------------
3 6 3 3 7 3 8 3 4 2 2 3
24x x x x x + 24x x x x + 24x x x x x + 41x x x x x x x -
1 2 3 8 9 2 3 8 9 1 2 3 8 9 1 2 3 4 6 8 9
-----------------------------------------------------------------------
2 3 3 3 3 2 4 3 3 3 4 3 4 4 3
48x x x x x x x + 31x x x x x x + 24x x x x x + 24x x x x x x +
1 2 3 4 6 8 9 1 2 3 6 8 9 2 3 6 8 9 1 2 3 6 8 9
-----------------------------------------------------------------------
2 6 3 3 2 5 4 4 6 4 4 6 4 2 7 4 2 8 4
48x x x x x x + 24x x x x + 8x x x - 24x x x - 32x x x x - 8x x x
1 2 4 6 8 9 1 2 3 9 1 3 9 2 3 9 1 2 3 9 1 3 9
-----------------------------------------------------------------------
2 3 2 2 4 2 4 2 2 4 2 3 2 4 2 2 2 3 4
- 41x x x x x x + 36x x x x x - 38x x x x x x x - 17x x x x x x +
1 2 3 4 6 9 1 3 4 6 9 1 2 3 4 5 6 9 1 2 3 4 6 9
-----------------------------------------------------------------------
3 3 3 4 2 4 3 4 5 3 4 3 2 3 4 4 2 4 4
20x x x x x + 4x x x x x + 4x x x x x - 31x x x x x x - 24x x x x
1 3 4 6 9 2 3 4 6 9 1 3 4 6 9 1 2 3 5 6 9 2 3 6 9
-----------------------------------------------------------------------
2 3 4 4 2 4 4 4 2 5 4
- 20x x x x x + 4x x x x - 48x x x x x x )
1 2 3 6 9 1 3 6 9 1 2 4 5 6 9
o23 : Ideal of S
|
i24 : chooseGoodMinors(1, 6, M, J, Strategy=>GRevLexSmallest)
4 2 3 2 2 2
o24 = ideal(x x - 2x x x x + x x x )
3 5 2 3 5 6 2 3 6
o24 : Ideal of S
|
i25 : chooseGoodMinors(1, 6, M, J, Strategy=>GRevLexSmallestTerm)
4 2 3 2 2 2
o25 = ideal(- x x + 2x x x x - x x x )
2 4 1 2 4 5 1 2 5
o25 : Ideal of S
|
i26 : chooseGoodMinors(1, 6, M, J, Strategy=>GRevLexLargest)
9 3 3 2 8 2 4 2 2 7 5 2 3 6 6 2
o26 = ideal(8x x x x x - 32x x x x x x + 40x x x x x x - 16x x x x x -
3 4 6 7 9 1 3 4 6 7 9 1 3 4 6 7 9 1 3 6 7 9
-----------------------------------------------------------------------
9 4 2 2 8 3 3 2 2 7 2 4 2 3 6 5 2
8x x x x x + 24x x x x x x - 8x x x x x x - 24x x x x x x +
3 4 6 7 9 1 3 4 6 7 9 1 3 4 6 7 9 1 3 4 6 7 9
-----------------------------------------------------------------------
4 5 6 2 8 4 2 3 2 7 3 3 3 3 6 2 4 3
16x x x x x + 8x x x x x - 32x x x x x + 40x x x x x -
1 3 6 7 9 1 3 4 6 9 1 3 4 6 9 1 3 4 6 9
-----------------------------------------------------------------------
4 5 5 3
16x x x x x )
1 3 4 6 9
o26 : Ideal of S
|
i27 : chooseGoodMinors(1, 6, M, J, Strategy=>Points)
3 2 4 3 6
o27 = ideal(12x x x - 4x x )
3 7 9 3 9
o27 : Ideal of S
|
Here the $1$ passed to the function says how many minors to compute. For instance, let's compute 8 minors for each of these strategies and see if that was enough to verify that the ring is regular in codimension 1. In other words, if the dimension of $J$ plus the ideal of partial minors is $\leq 1$ (since $S/J$ has dimension 3).
i28 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>Random))
-- used 0.0703475 seconds
o28 = 2
|
i29 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>LexSmallest))
-- used 0.332843 seconds
o29 = 2
|
i30 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>LexSmallestTerm))
-- used 0.450347 seconds
o30 = 0
|
i31 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>LexLargest))
-- used 0.578471 seconds
o31 = 2
|
i32 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>GRevLexSmallest))
-- used 0.22062 seconds
o32 = 3
|
i33 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>GRevLexSmallestTerm))
-- used 0.261519 seconds
o33 = 3
|
i34 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>GRevLexLargest))
-- used 0.243075 seconds
o34 = 3
|
i35 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>Points))
-- used 15.9947 seconds
o35 = 1
|
Indeed, in this example, even computing determinants of 1,000 random submatrices is not typically enough to verify that $V(J)$ is regular in codimension 1. On the other hand, Points is almost always quite effective at finding valuable submatrices, but can be quite slow. In this particular example, we can see that LexSmallestTerm also performs very well (and does it quickly). Since different strategies work better or worse on different examples, the default strategy actually mixes and matches various strategies. The default strategy, which we now elucidate,
i36 : peek StrategyDefault
o36 = OptionTable{GRevLexLargest => 0 }
GRevLexSmallest => 16
GRevLexSmallestTerm => 16
LexLargest => 0
LexSmallest => 16
LexSmallestTerm => 16
Points => 0
Random => 16
RandomNonzero => 16
|
says that we should use GRevLexSmallest, GRevLexSmallestTerm, LexSmallest, LexSmallestTerm, Random, RandomNonzero all with equal probability (note RandomNonzero, which we have not yet discussed chooses random submatrices where no row or column is zero, which is good for working in sparse matrices). For instance, if we run:
i37 : time chooseGoodMinors(20, 6, M, J, Strategy=>StrategyDefault, Verbose=>true);
internalChooseMinor: Choosing GRevLexSmallest
internalChooseMinor: Choosing LexSmallestTerm
internalChooseMinor: Choosing LexSmallestTerm
internalChooseMinor: Choosing LexSmallestTerm
internalChooseMinor: Choosing LexSmallestTerm
internalChooseMinor: Choosing LexSmallestTerm
internalChooseMinor: Choosing Random
internalChooseMinor: Choosing RandomNonZero
internalChooseMinor: Choosing LexSmallestTerm
internalChooseMinor: Choosing GRevLexSmallest
internalChooseMinor: Choosing Random
internalChooseMinor: Choosing GRevLexSmallestTerm
internalChooseMinor: Choosing LexSmallest
internalChooseMinor: Choosing LexSmallestTerm
internalChooseMinor: Choosing GRevLexSmallestTerm
internalChooseMinor: Choosing GRevLexSmallestTerm
internalChooseMinor: Choosing LexSmallest
internalChooseMinor: Choosing LexSmallestTerm
internalChooseMinor: Choosing GRevLexSmallestTerm
internalChooseMinor: Choosing Random
internalChooseMinor: Choosing Random
internalChooseMinor: Choosing RandomNonZero
chooseGoodMinors: found =20, attempted = 22
-- used 0.54474 seconds
o37 : Ideal of S
|
we can see different minors being chosen via different strategies.
Note, if one asks chooseGoodMinors for more than one minor, then any time a Points strategy is selected, the point is found on $J$ plus the ideal of all minors computed thus far.
Let us take a look at some other built-in strategies.
i38 : peek StrategyDefaultNonRandom
o38 = OptionTable{GRevLexLargest => 0 }
GRevLexSmallest => 25
GRevLexSmallestTerm => 25
LexLargest => 0
LexSmallest => 25
LexSmallestTerm => 25
Points => 0
Random => 0
RandomNonzero => 0
|
i39 : peek StrategyDefaultWithPoints
o39 = OptionTable{GRevLexLargest => 0 }
GRevLexSmallest => 16
GRevLexSmallestTerm => 16
LexLargest => 0
LexSmallest => 16
LexSmallestTerm => 16
Points => 32
Random => 0
RandomNonzero => 0
|
i40 : peek StrategyPoints
o40 = OptionTable{GRevLexLargest => 0 }
GRevLexSmallest => 0
GRevLexSmallestTerm => 0
LexLargest => 0
LexSmallest => 0
LexSmallestTerm => 0
Points => 100
Random => 0
RandomNonzero => 0
|
StrategyDefaultNonRandom is like StrategyDefault but removes random submatrices (which can be suprisingly beneficial in some cases). StrategyDefaultWithPoints removes randomness but adds in points instead.
A warning on chooseGoodMinors: The strategies LexSmallest and LexSmallestTerm will very frequently repeatedly choose the same submatrix of the given matrix. Hence if one tries to run chooseGoodMinors and choose too many minors with such a strategy, one can get into a long loop (the function give up eventually, but only after doing way too much work). The GRevLex strategies periodically temporarily change the underlying matrix to avoid this sort of loop.
Points: Notice that Strategy => StrategyPoints and Strategy => Points do the same thing. We briefly describe how chooseGoodMinors interacts with Points. Indeed Points forms the ideal of minors computed so far (plus $J$), finds a point where that ideal vanishes (which can be slow), evaluates the matrix $M$ at that point, and then finally computes the corresponding determinant of the submatrix. This submatrix will always produce a minor which shrinks our vanishing locus.
By default, the Points strategy actually finds geometric points. Which can be sometimes slower (but which are almost certain to exist, and are less likely to hang if the function has trouble finding a point). For instance, we can control that as follows.
i41 : ptsStratGeometric = new OptionTable from (options chooseGoodMinors)#PointOptions; |
i42 : ptsStratGeometric#ExtendField --look at the default value o42 = true |
i43 : time dim (J + chooseGoodMinors(1, 6, M, J, Strategy=>Points, PointOptions=>ptsStratGeometric))
-- used 1.16801 seconds
o43 = 2
|
i44 : ptsStratRational = ptsStratGeometric++{ExtendField=>false} --change that value
o44 = OptionTable{DecompositionStrategy => Decompose}
DimensionFunction => dim
ExtendField => false
Homogeneous => false
NumThreadsToUse => 1
PointCheckAttempts => 0
Replacement => Binomial
Strategy => Default
Verbose => false
o44 : OptionTable
|
i45 : ptsStratRational.ExtendField --look at our changed value o45 = false |
i46 : time dim (J + chooseGoodMinors(1, 6, M, J, Strategy=>Points, PointOptions=>ptsStratRational))
-- used 2.15114 seconds
o46 = 2
|
Other options may also be passed to the RandomPoints package via the PointOptions option.
regularInCodimension: It is reasonable to think that you should find a few minors (with one strategy or another), and see if perhaps the minors you have computed so far are enough to verify our ring is regular in codimension 1. This is exactly what regularInCodimension does. One can control at a fine level how frequently new minors are computed, and how frequently the dimension of what we have computed so far is checked, by the option codimCheckFunction. For more on that, see RegularInCodimensionTutorial and regularInCodimension. Let us finish running regularInCodimension on our example with several different strategies.
i47 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>StrategyDefault)
-- used 3.08543 seconds
o47 = true
|
i48 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>StrategyDefaultNonRandom)
-- used 0.881896 seconds
o48 = true
|
i49 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>Random)
-- used 5.97019 seconds
|
i50 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>LexSmallest)
-- used 2.91023 seconds
|
i51 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>LexSmallestTerm)
-- used 0.50912 seconds
o51 = true
|
i52 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>GRevLexSmallest)
-- used 3.16568 seconds
|
i53 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>GRevLexSmallestTerm)
-- used 3.91789 seconds
|
i54 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>Points)
-- used 11.0609 seconds
o54 = true
|
i55 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>StrategyDefaultWithPoints)
-- used 10.2804 seconds
o55 = true
|
If regularInCodimension outputs nothing, then it couldn't verify that the ring was regular in that codimension. We set MaxMinors => 100 to keep it from running too long with an ineffective strategy. Again, even though GRevLexSmallest and GRevLexSmallestTerm are not effective in this particular example, in others they perform better than other strategies. Note similar considerations also apply to projDim.
The object FastMinorsStrategyTutorial is a symbol.