Description
Many of the core functions of this package allow the user to fine tune the strategy used for selecting submatrices. Different strategies yield markedly different performance or results on various examples. These are controlled by specifying a
Strategy => option, pointing to a
HashTablewhich specifies several strategies should be used simultaneously, or to a symbol saying we should use only a single strategy. For a more detailed look at this in an example please see
FastMinorsStrategyTutorialBefore describing the available strategies, we begin by roughly outlining the different approaches.

Heuristic submatrix selection: In this case, a submatrix is chosen via a greedy algorithm, looking for a submatrix with smallest (or largest) degree with respect to a random monomial order.

Submatrix selection via rational and geometric points: Here a rational or geometric point is found where a given ideal vanishes. That point is plugged into the matrix and a submatrix of full rank is identified. This approach currently only works over a finite field and is accomplished with the help of the package RandomPoints.

Random submatrix selection: This either chooses a completely random submatrix, or a submatrix which has no zero columns or rows.
There we highlight five preprogrammed strategies provided to the user.

StrategyDefault: this uses a mix of heuristics and random submatrices.

StrategyRandom: this uses purely random submatrices.

StrategyDefaultNonRandom: this uses a mix of heuristics but no random submatrices.

StrategyPoints: this only uses rational / geometric points to find submatrices.

StrategyDefaultWithPoints: this uses a mix of heuristics and submatrices chosen with rational and geometric points.
Below the details of how these strategies are constructed will be detailed below. But first, we provide an example showing that these strategies can perform quite differently. The following is the cone over the product of two elliptic curves. We verify that this ring is regular in codimension 1 using different strategies. Essentially, minors are computed until it is verified that the ring is regular in codimension 1.
i1 : T=ZZ/7[a..i]/ideal(f*he*i,c*hb*i,f*gd*i,e*gd*h,c*ga*i,b*ga*h,c*eb*f,c*da*f,b*da*e,g^3h^2*ig*i^2,d*g^2e*h*id*i^2,a*g^2b*h*ia*i^2,d^2*ge^2*id*f*i,a*d*gb*e*ia*f*i,a^2*gb^2*ia*c*i,d^3e^2*fd*f^2,a*d^2b*e*fa*f^2,a^2*db^2*fa*c*f,c^3+f^3i^3,b*c^2+e*f^2h*i^2,a*c^2+d*f^2g*i^2,b^2*c+e^2*fh^2*i,a*b*c+d*e*fg*h*i,a^2*c+d^2*fg^2*i,b^3+e^3h^3,a*b^2+d*e^2g*h^2,a^2*b+d^2*eg^2*h,a^3+e^2*f+d*f^2h^2*ig*i^2);

i2 : elapsedTime regularInCodimension(1, T, Strategy=>StrategyDefault)
 2.99803 seconds elapsed
o2 = true

In this particular example, on one machine, we list average time to completion of each of the above strategies after 100 runs.

StrategyDefault: 1.65 seconds

StrategyRandom: 8.32 seconds

StrategyDefaultNonRandom: 0.99 seconds

StrategyPoints: 3.27 seconds

StrategyDefaultWithPoints: 3.37
Roughly speaking, heuristics tend to provide more information than random submatrices and so they work much faster since they consider far fewer submatrices. Frequently also, computing random or rational points does have advantages as typically fewer still minors are needed (hence if computing minors is slow
StrategyPoints is a good choice). However, sometimes that nontrivial point computation will become stuck (in the above example, the median time for
StrategyPoints and
StrategyDefaultWithPoints was close to 1.5 seconds, but a couple runs in each case were orders of magnitude slower).
Custom StrategiesThe user can create their own strategies as well, as we now explain. In particular, the user can even customize the heuristics used. See below for how to easily use only a single heuristic. To custom strategy is specified by a
HashTable which must have the following keys.

GRevLexLargest: try to find submatrices where each row and column has a large entry with respect to a random GRevLexorder.

GRevLexSmallest: try to find submatrices where each row and column has a small entry with respect to a random GRevLexorder.

GRevLexSmallestTerm: find submatrices where each row and column has an entry with a small term with respect to a random GRevLexorder.

LexLargest: try to find submatrices where each row and column has a large entry with respect to a random Lexorder.

LexSmallest: try to find submatrices where each row and column has a small entry with respect to a random Lexorder.

LexSmallestTerm: find submatrices where each row and column has an entry with a small term with respect to a random Lexorder.

Random: find random submatrices

RandomNonzero: find random submatrices that have nonzero rows and columns

Points: find submatrices that are not singular at the given ideal by finding a point where that ideal vanishes, and evaluating the matrix at that point (via the package RandomPoints). If working over a characteristic zero field, this will select random submatrices. To access options for that package, set the PointOptions option.
For example:
i3 : peek StrategyDefault
o3 = OptionTable{GRevLexLargest => 0 }
GRevLexSmallest => 16
GRevLexSmallestTerm => 16
LexLargest => 0
LexSmallest => 16
LexSmallestTerm => 16
Points => 0
Random => 16
RandomNonzero => 16

Each such key should point to an integer. The larger the integer, the more likely that such a minor will be chosen.
Functions such as
chooseGoodMinors will select a number of random submatrices based on the values of those keys. For example, if
LexSmallest and
LexLargest are set to
50 approximately the submatrics will be smallest with respect to
Lex and the other half will be largest with respect to
Lex.The values do not need to add up to 100.
The heuristic functions all work by finding the optimal entry with respect to the given strategy, removing that row and column, and then choosing the next optimal entry. This is done until a submatrix of the desired size has been found.
In some functions, the
GRevLex versions of this strategy will modify the working matrix in a loop, repeatedly lowering/raising the degree of elementsso as to ensure that different choices are made.
We briefly summarize the Strategies provided to the user by default (some of which we have seen in action above)

StrategyDefault: 16% of the matrices are LexSmallest, LexSmallestTerm, GRevLexSmallest, GRevLexLargest, Random, and RandomNonZero each

StrategyDefaultNonRandom: 25% of the matrices are LexSmallest, LexSmallestTerm, GRevLexSmallest and, GRevLexLargest each

StrategyLexSmallest: 50% of the matrices are LexSmallest and 50% are LexSmallestTerm

StrategyGRevLexSmallest: 50% of the matrices are GRevLexSmallest and 50% are GRevLexLargest

StrategyRandom: chooses 100% random submatrices.

StrategyPoints: choose all submatrices via Points.

StrategyDefaultWithPoints: like StrategyDefault but replaces the Random and RandomNonZero submatrices as with matrices chosen as in Points.
Additionally, a
MutableHashTable named
StrategyCurrent is also exported. It begins as the default strategy, but the user can modify it.
Using a single heuristic Alternatively, if the user only wants to use say
LexSmallestTerm they can set,
Strategy to point to that symbol, instead of a creating a custom strategy HashTable. For example:
i4 : elapsedTime regularInCodimension(1, T, Strategy=>LexSmallestTerm)
 1.42472 seconds elapsed
o4 = true
