# FastMinorsStrategyTutorial -- How to use and construct strategies for selecting submatrices in various functions

## Description

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 = {{4, 3, 5, 0, 8, 2}, {20, 21, 19, 16, 12, 17}} o18 : List i19 : M^(h#0)_(h#1) o19 = {1} | x_6^3 0 0 -x_2x_6 -2x_5x_9 {1} | 0 x_6^3 0 2x_1x_4 2x_4x_7-x_6x_9 {1} | 3x_5x_6^2 3x_4x_6^2 4x_6^3 -x_2x_5-2x_1x_6 -x_4x_9 {1} | 0 x_3^3 0 x_4^2-x_6^2 0 {1} | -3x_8x_9^2 -3x_7x_9^2 -4x_9^3 0 -x_5^2-x_4x_6 {1} | 3x_2x_3^2 3x_1x_3^2 4x_3^3 0 0 ----------------------------------------------------------------------- 0 | x_1^2 | -x_2^2-x_1x_3 | 2x_1x_4-x_3x_6 | 0 | -x_1x_6 | 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 5 4 8 4 5 2 7 3 6 3 6 2 7 4 5 8 o26 = ideal(16x x x + 23x x x x - 46x x x x + 46x x x x - 23x x x x - 3 8 9 2 3 8 9 2 3 8 9 2 3 8 9 2 3 8 9 ----------------------------------------------------------------------- 5 4 9 16x x x ) 2 3 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.137351 seconds o28 = 2 i29 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>LexSmallest)) -- used 0.75069 seconds o29 = 2 i30 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>LexSmallestTerm)) -- used 0.902399 seconds o30 = 0 i31 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>LexLargest)) -- used 1.16942 seconds o31 = 2 i32 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>GRevLexSmallest)) -- used 0.583461 seconds o32 = 3 i33 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>GRevLexSmallestTerm)) -- used 0.670918 seconds o33 = 3 i34 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>GRevLexLargest)) -- used 0.474326 seconds o34 = 3 i35 : time dim (J + chooseGoodMinors(8, 6, M, J, Strategy=>Points)) -- used 30.4343 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 LexSmallest 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 GRevLexSmallest internalChooseMinor: Choosing Random internalChooseMinor: Choosing GRevLexSmallest internalChooseMinor: Choosing GRevLexSmallest internalChooseMinor: Choosing LexSmallestTerm internalChooseMinor: Choosing GRevLexSmallest internalChooseMinor: Choosing Random internalChooseMinor: Choosing GRevLexSmallest internalChooseMinor: Choosing LexSmallestTerm internalChooseMinor: Choosing LexSmallestTerm internalChooseMinor: Choosing GRevLexSmallest chooseGoodMinors: found =20, attempted = 21 -- used 1.25751 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 surprisingly 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 2.37707 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 7.90494 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 5.26964 seconds o47 = true i48 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>StrategyDefaultNonRandom) -- used 1.63045 seconds o48 = true i49 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>Random) -- used 8.86616 seconds i50 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>LexSmallest) -- used 5.72247 seconds i51 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>LexSmallestTerm) -- used 0.930428 seconds o51 = true i52 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>GRevLexSmallest) -- used 6.93983 seconds i53 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>GRevLexSmallestTerm) -- used 8.89159 seconds i54 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>Points) -- used 24.7192 seconds o54 = true i55 : time regularInCodimension(1, S/J, MaxMinors => 100, Strategy=>StrategyDefaultWithPoints) -- used 28.2549 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.