>
> I have added some documentation to permgrps in patch here:
> https://github.com/martinbaker/fricasAlgTop/blob/master/permgrps2.patch
>
> This contains documentation only, no code changes.
>
> By 'documentation' I mean comments + literate.
> By 'literate' I mean formatted text. I have not tried to follow literate
> methodology, that is, I have not tried to make a linear story. This is
> purely intended as reference information which would otherwise go in
> comments. This just saves lots of lines starting with '--'.
>
> I don't know how you feel about a third party (me) writing comments for
> other peoples code? Although people here are very good at replying to
> requests for information on this forum there does not seem to be much
> enthusiasm for adding to documentation in a more permanent and easily
> found way?
>
> I don't feel qualified to try to speak for the original authors but I
> don't think they provided enough information to be able to use or
> develop the software without spending a lot of time tracing through the
> code to discover its secrets. I think it is very wasteful for every
> potential user to have to do this. I was therefore motivated to write
> these notes. Such information (or better if you can improve it) needs to
> be in a place where users and developers can find it.
>
> I did find some other sources for information about the
> Schreier-Sims algorithm such as this:
> https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorithm
>
> Waldek Hebisch referred to these notes by A. Hulpke which contain a
> sketch of the algorithm.
> http://www.math.colostate.edu/~hulpke/CGT/cgtnotes.pdf
>
> Waldeks description on FriCAS forum here:
> https://groups.google.com/forum/?hl=en#!topic/fricas-devel/EtLwgd2dWNU
>
> I find it improves the documentation to use diagrams, I have
> therefore put much better documentation on the web page here:
> http://www.euclideanspace.com/prog/scratchpad/mycode/discrete/finiteGroup/
>
> I think it is worth studying permgrps.spad even if someone is not
> interested in developing group related code, this still looks to me like
> a good case study in how to design code to scale up to very large
> structures. So perhaps it is worth documenting for that reason alone.
Some comments about this patch:
1) I am against putting large amount of text into code files.
One reason is ease of finding things: for finding things
I depend on grep. Free text complicates grep searches
because it tends to produce false positives. Another
reason is separation of concerns: documentation tends to
have separate life cycle from code. I have seen arguments
that code and documentation should be written together,
but AFAICS trying to do both at the same time dumps
productivity quite a lot. And in practice when code
implements existing algorithm, then this existing
algorithm means that some for of documentation
exists befor code. Sometimes algorithm is discovered
by experimenting with code. In such case during
code developement there are false choices that must
be retracted later. It does not much sense to
document them. In particular false choices are
correlated with wrong expectations so documentation
created at that time with high probability would be
wrong. So in such case it is natural that documentation
(or significant part of it) comes after code. During
later developement also there is high chance that changes
to code and documentation are independent.
2) Good documentation is welcome. However it is pretty hard
to write good documentation. One does not need to be
original author, but it takes specific skill to
write useful documentation. It requires both good
understading of topic and of potential difficulties
of readers.
3) Coming back to specific question of Schreir-Sims algorithm.
This algorithm is described in A. Seress book "Permutation
group algorithms". IMO this is quite good description.
AFAICS think this book is not freely available. Once
somebody understands the algorithm tracking code should
be relatively easy -- code basicaly is doing what
algorithm prescribes. There are few implementation choices,
concerning how to efficiently implement some steps. Seress
discusses possible alternatives. I have no access to Sims
article, but my Univerity have Seress book. So there
is good documentation for the permgrps, just it is not
freely available.
4) Concerning your text: there are inaccuracies (for example
scalable methods exist for matrix groups), there are
missing important points, some passage look completely
wrong, like:
+The use of the Vector domain for this does seem to be stretching
+the FriCAS type system a bit. For instance elements of subgroup are
+coded as a vector of a vector (Vector Vector NNI) which would not be
+valid if the type system were fully checked but presumably gets away
+with it because vectors are defined over Type.
Vector(NNI) stores nonnegative integers and provides 1 based
indexing. We do not need most operations provided by Vector,
in particular we do not need vector addition or multiplication
by scalars but that is OK: we use what Vector provides and
nothing more. In other words, we could probably just use arrays
here (but IIRC there was some useful function that only accepted
vectors and did not work on arrays). And using arrays or
vectors to store permutations is a standard trick allowing
resonably fast operations on permutations.
OK, enough for now.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
