CWatset Algorithms and Data Structures
Share Package for GAP

  Or Here
  SourceForge Logo
  CWADS (CWatset Algorithms and Data Structures) is a share package for the computer algebra system GAP (Groups, Algorithms, and Programming) which performs useful computations with cwatsets. Right now CWADS is in beta, and only implements the bare infastructure. Keep in mind that, until there is a version 1 release, this infastructure may change drastically. Other than some scripts, there has never before been a computer algebra system for working with cwatsets, and there is some question as to what is the most efficient means of storing them internally. GAP provides a very sophisticated means of working with different internal representations and for optimizing algorithms for different representations, and CWADS should take full advantage of this.

There are some serious things to think about at the currect stage of development. These serious things should probably be included in some sort of TODO file with the release, but they're not. They should also merit their own web page, but the page is as yet quite small. Right now, cwatsets have a working data structure that is able to determine (relatively quickly) whether or not a given collection is a cwatset. The package can also do some of the cwatset arithmetic, such as actions by external elements, and typical set operations. The goal for a 1.0 release is to have full group functionality. That is, to be able to determine (quickly) such things as the omega group, representation group, etc. There are a number of things holding this back.

First, the omega group can be thought of as a wreath product or a semidirect product, whichever one prefers. Since I am not currently using GAP's Cartesian product mechanism for my binary words (more on that in the next paragraph), it is more useful to think of a semidirect product. The problem is that binary words (with enough closure) constitute an additive group. GAP isn't particularly fond of additive groups, which is making the process difficult. One possible work-around is to define a custom "omega pair" data type. I don't like this, because it is getting too far from GAP's core functionality.

On a similar note, I have already gotten away from GAP's core functionality in a way I don't like. The binary word is defined as a custom data type. There are three reasons for this, the first not being very good, and the last being the real hang-up. First, one might suppose some optimization can occur, since we don't have the overhead of thinking of a generalized sequence. Indeed, the binary word is actually stored with booleans, which should be quite fast. This is not a very good reason, however, since any performance gain is negligable, and there may not be performance gain, since using GAP's built-in tupling probably has kernel-level optimizations. The second reason is that defining custom data structures makes defining certain other things (like the ordering we prefer to use) relatively easy. This is not a good enough reason alone. The third reason is that, again, GAP doesn't seem to like additive systems. This is very annoying, and has constantly been the biggest problem I've had in developing CWADS.

Please, if anybody knows GAP better than I do and knows how to get group products to work nicely with additive systems, email me.