1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

********** PPrroojjeecctt NNeewwss **********
The dates are given in the format YYYYMMDD. More details can be found in the
_C_h_a_n_g_e_L_o_g.
2200004411000077 New release with unimportant changes. Release is mainly for syncing
the main release files with te Debian package.
2200004400991111 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.
2200004400881199 The socalled 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.
2200004400881100 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.
2200004400773300 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 GAPconnected 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.
2200004400771144 The SchreierToddCoxeterSims 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
2200004400770088 The implementation of SchreierToddCoxeterSims 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.
2200004400770077 Made an implementation of random element generation using the Rattle
algorithm by LeedhamGreen, to avoid using GAP:s builtin algorithm
(which is Shake). This way some inverse matrix calculations are
avoided.
Also included is a not yet finished implementation of SchreierTodd
CoxeterSims algorithm, which uses coset enumeration to possibly
decrease the number of Schreier generators that are considered at
each level of the standard SchreierSims algorithm.
2200004400770033 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.
2200004400662299 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 GAPrelated 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
2200004400662266 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.
2200004400662244 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 onedimensional subspace (ie the
line) containing it, and the projective action of the group is used
on this line.
2200004400220099 Implemented a more efficient version, using explicit levels and the
trick of stripping Schreier generators. Code seems to be more than
twice as fast.
2200004400111177 A seemingly working version of SchreierSims has now been
implemented. It is the standard naive version without any
optimisations.
