********** PPrroojjeecctt NNeewwss **********
The dates are given in the format YYYY-MM-DD. More details can be found in the
_C_h_a_n_g_e_L_o_g.
22000044--1100--0077 New release with unimportant changes. Release is mainly for syncing
the main release files with te Debian package.
22000044--0099--1111 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.
22000044--0088--1199 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.
22000044--0088--1100 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.
22000044--0077--3300 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.
22000044--0077--1144 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
22000044--0077--0088 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.
22000044--0077--0077 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.
22000044--0077--0033 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.
22000044--0066--2299 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.
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
22000044--0066--2266 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.
22000044--0066--2244 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.
22000044--0022--0099 Implemented a more efficient version, using explicit levels and the
trick of stripping Schreier generators. Code seems to be more than
twice as fast.
22000044--0011--1177 A seemingly working version of Schreier-Sims has now been
implemented. It is the standard naive version without any
optimisations.