next | previous | forward | backward | up | top | index | toc | Macaulay2 website
FastMinors :: StrategyDefault

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 begin by roughly outlining the different approaches. There we highlight five pre-programmed strategies provided to the user. 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.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. 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. 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) 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

For the programmer

The object StrategyDefault is an option table.