File: NEWS

package info (click to toggle)
gap-matrix-schreiersims 0.9.20041122-3.1
  • links: PTS
  • area: main
  • in suites: lenny
  • size: 716 kB
  • ctags: 47
  • sloc: makefile: 144
file content (99 lines) | stat: -rw-r--r-- 6,758 bytes parent folder | download | duplicates (2)
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 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.