This page contains a discussion on the two algorithms that are used in the function primaryInvariants, which computes a homogeneous system of parameters (hsop) for the invariant ring R:=K[x1,...,xn]G of a finite group G. Which algorithm is used depends on the Boolean value the optional argument Dade takes. In the case where it is set to false it uses what shall be referred to as the 'default' algorithm. If it is set to true then it uses what shall be called the 'Dade' algorithm.
The default algorithm is an implementation of the 'optimal' algorithm given in [K]. It is optimal in the sense that it finds a hsop f1,...,fn such that the number of secondary invariants required to make R into a free K[f1,...,fn]-module is minimal. The first step in the default algorithm is to cycle through the List s={d1,...,dn} of possible degrees for the hsop. It tests the degrees against two restrictions that are known to hold for any hsop of R: firstly, the order of G must divide the product d1*...*dn and secondly, the polynomial H(R,T)*(1-Td1)*...*(1-Tdn) must lie in ZZ[T], where H(R,T) is the Molien (Hilbert) series of R [DK, p83]. Once a List of suitable degrees is found, the algorithm uses a Krull-dimension based test that holds for algebras over infinite fields to determine the existence of a hsop with the candidate degrees; see [K, Theorem 2]. It then finds such a hsop if one exists, or tries a new List of degrees if such a hsop does not exist. Note: if one knows a priori that a hsop exists for some List of degrees, this can be assigned to the optional argument DegreeVector and the default algorithm will compute a hsop with degrees corresponding to this List. Finally, users should be aware that the default algorithm currently only works in the case where R is defined over a field of characteristic zero.
The Dade algorithm is simpler than the default algorithm. It first constructs a Dade basis v1,...,vn for the dual space V* spanned by x1,...,xn. Then for each i, it computes the polynomial fi defined as the product over the G-orbit of vi. The resulting collection f1,...,fn is a hsop for R; see [DK, pp80,81]. In the implemented Dade algorithm, a Dade basis is constructed iteratively by choosing random linear forms such that vi is not contained in any of the vector subspaces spanK{w1,...,wi-1}, where wj is in the G-orbit of vj. The Dade algorithm can work with the case of finite fields, provided that the field is large enough to ensure Kn cannot be filled by the union of the subspaces mentioned in the construction of the Dade basis. A sufficient, though not necessarily optimal, requirement is that |K|>|G|n-1. Because of the random generation involved in the construction of a Dade basis, the Dade algorithm will generally output n primary invariants of degrees equalling the order of G that have ugly coefficients.
The example below provides a good comparison of the two different algorithms and their relative merits.
|
|
|
The two algorithms used in primaryInvariants are timed. One sees that the Dade algorithm is faster, however the primary invariants output are all of degree 8 and have ugly coefficients.
|
|
The extra work done by the default algorithm to ensure an optimal hsop is rewarded by needing to calculate a smaller collection of corresponding secondary invariants. In fact, it has proved quicker overall to calculate the invariant ring based on the optimal algorithm rather than the Dade algorithm.
|
|
|
Of course, currently one advantage of the Dade algorithm is that it can calculate a hsop for the invariant ring when considering a finite field. Since |C4xC2|2=64, it is safe to consider the finite field with 101 elements.
|
|
|
References
[DK] Derksen, H., Kemper, G. Computational Invariant Theory. Berlin Heidelberg New York: Springer-Verlag, 2002
[K] Kemper, G. An Algorithm to Calculate Optimal Homogeneous Systems of Parameters. J. Symbolic Computation 27 (1999), 171-184