# StrategyDefault -- strategies for choosing submatrices

## 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 beging 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 pre-programmed 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*h-e*i,c*h-b*i,f*g-d*i,e*g-d*h,c*g-a*i,b*g-a*h,c*e-b*f,c*d-a*f,b*d-a*e,g^3-h^2*i-g*i^2,d*g^2-e*h*i-d*i^2,a*g^2-b*h*i-a*i^2,d^2*g-e^2*i-d*f*i,a*d*g-b*e*i-a*f*i,a^2*g-b^2*i-a*c*i,d^3-e^2*f-d*f^2,a*d^2-b*e*f-a*f^2,a^2*d-b^2*f-a*c*f,c^3+f^3-i^3,b*c^2+e*f^2-h*i^2,a*c^2+d*f^2-g*i^2,b^2*c+e^2*f-h^2*i,a*b*c+d*e*f-g*h*i,a^2*c+d^2*f-g^2*i,b^3+e^3-h^3,a*b^2+d*e^2-g*h^2,a^2*b+d^2*e-g^2*h,a^3+e^2*f+d*f^2-h^2*i-g*i^2); i2 : elapsedTime regularInCodimension(1, T, Strategy=>StrategyDefault) -- 2.32066 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 non-trivial 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 Strategies
The 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) -- 0.216888 seconds elapsed o4 = true

## For the programmer

The object StrategyDefault is .