The dates are given in the format YYYY-MM-DD. More details can be found in the ChangeLog.
| 2004-09-11 | A somewhat complete manual now exists, and the code has had some cosmetic updates and more documentation. The package is now considered to be in beta stage, and the Debian packages has been somewhat changed. |
|---|---|
| 2004-08-19 |
The so-called Verify routine by Sims has been implemented, from the
description in Seress book. This seems to be a better strong
generating test than the STCS algorithm, and one can now choose
between them with an Option when using the probabilistic
algorithm. The Verify algorithm is still neither cleaned up nor
optimised in any way, so it is not fast, but it appears to be both
sound and complete. The probabilistic algorithm now again uses the GAP function PseudoRandom to generate random group elements, since further testing has indicated that this is the fastest method, even though we have to calculate inverse matrices for the elements returned by this function. |
| 2004-08-10 |
An algorithm highly inspired by the nearly linear time algorithm,
described in Seress book as well as in the 1991 paper by Babai et al,
has been implemented. Some parts of the nearly linear time algorithm
has not yet been implemented though, in particular the "short Schreier
trees". The implementation is still very slow, though, so the fastest
version is still the standard deterministic algorithm. Other changes include the use of random subproducts in the probabilistic algorithm, instead of random elements computed using the Rattle algorithm. The representation of Schreier trees has been somewhat augmented, to include the depth of each node, as well as the height of the tree. There is a possibility to create shallow Schreier trees, which are guaranteed to have at most logarithmic depth. These changes are described in Seress book as well as in the above paper, and are needed in the nearly linear time algorithm. |
| 2004-07-30 | A rudimentary manual has been created, and it is both included in the package distribution and available from the package homepage. The code is now more GAP-connected in the sense that the algorithms are methods of an operation StabChainMatrixGroup and the package installs a method for the Size attribute for finite matrix groups that uses that attribute to compute the order of a group. |
| 2004-07-14 |
The Schreier-Todd-Coxeter-Sims algorithm has been optimized and the
handling of relations has been fixed. Homomorphisms are now only used when
needed, and otherwise normal lists are used to map generator matrices to
each corresponding free group. The package is now also available as a Debian package, and is advertised on freshmeat.net |
| 2004-07-08 | The implementation of Schreier-Todd-Coxeter-Sims algorithm seems to be working now. It is however still very slow, and there are possibly some mistakes in the handling of relations, since it appears that the coset enumeration never finishes successfully. |
| 2004-07-07 |
Made an implementation of random element generation using the Rattle algorithm
by Leedham-Green, to avoid using GAP:s built-in algorithm (which is Shake).
This way some inverse matrix calculations are avoided. Also included is a not yet finished implementation of Schreier-Todd-Coxeter-Sims algorithm, which uses coset enumeration to possibly decrease the number of Schreier generators that are considered at each level of the standard Schreier-Sims algorithm. |
| 2004-07-03 |
Implemented a simple (and yet slow) version of the random
Schreier-Sims algorithm, as first described by Leon. The algorithm
does not use any verification but takes as input a probability and
tries to achieve at least this probability of correctness. However,
since the group elements are probably not taken from a uniform
distribution (it uses GAP:s PseudoRandom function) there is no
theoretical guarantee of any probability. The stopping conditions used are simple: when a number of consecutive random elements sift to identity the algorithm terminates, and the number is calculated from the given probability. If lower and/or upper bounds on the group order are known, they are used in the algorithm. |
| 2004-06-29 | Added more Options to control when some features of the algorthim are used, sine it seems that, in particular, the tricks of extending Schreier trees and using alternating actions do not always make things go faster. Also incorporated some GAP-related improvements due to Alexander Hulpke, and a selection of an initial store of base points using a strategy of O'Brien and Murray. |
| 2004-06-26 | Added an Option to flatten the Schreier trees at creation time (make them have height 1), so that later only a single hash lookup is needed to find the orbit element for a given point. The Option is called "SimpleSchreierTree" and it seems to make the algorithm go faster by a factor 2. |
| 2004-06-24 | The trick of using alternating actions at different levels of the algorthim has now been implemented. Each base point in the initial partial base is preceded by the one-dimensional subspace (ie the line) containing it, and the projective action of the group is used on this line. |
| 2004-02-09 | Implemented a more efficient version, using explicit levels and the trick of stripping Schreier generators. Code seems to be more than twice as fast. |
| 2004-01-17 | A seemingly working version of Schreier-Sims has now been implemented. It is the standard naive version without any optimisations. |