Computational Group Theory at Colorado State University

Research

Research in Fort Collins covers many aspects of CGT. The following list gives some areas on which work has been done recently or is continuing:

• Classification of transitive permutation groups and subgroups of the symmetric group.
• Identification of Galois Groups.
• Improvements to group homomorphism and automorphism group calculations.
• Hybrid group representations and hybrid quotient algorithm. (Collaboration with B.EICK (Braunschweig, Germany) and A.NIEMEYER (Perth, Australia).
• User Support for GAP.
• Maintainance of a multitude of modules for GAP, e.g. permutation groups, finitely presented groups, hybrid algorithms for conjugacy classes and subgroups.
• Development of Teaching material and system improvements to enable use in the undergraduate curriculum.
• Constructive theory of discrete structures. Finite group actions. Orbit problems. Applications in Coding Theory, Design Theory and Finite Geometry.
• Algorithms for working with permutation groups and classical groups (i.e. matrix groups).

Some relevant publications can be found on this page.

Recent and current student and thesis projects include:

• Möbius functions for Symmetric Groups (K. Monks, MS2008), continuing work for PhD.
• Algorithms for automorphism groups (S. JONSDOTTIR, MS2004, PhD2008)
• Construction of Polycyclic Generating systems (E. ZILIAK, MS2006), continuing work for PhD.
• Improvements to discrete logarithm (Undergraduate Research S. GAGE, 2003).
• Shortest word expressions for elements (Undergraduate Research N. ROHRBACKER, 2004).

Studying

Computational Group Theory uses methods from Algebra and Combinatorics. If you are interested in doing research in this area, be it as undergraduate research, as masters thesis or as a doctoral thesis project, the following list gives some information on courses and prerequisites. Feel free to contact me if you have further questions.

Graduates: Typically incoming graduate students will start with the first-year courses on Algebra (M566/567) and Combinatorics (501/502) and continue with the second year courses (offered only every second year) on representation theory (M666). The courses on advanced combinatorics (M601/602) and commutative algebra (M667) are strongly recommended.
If you did not have linear algebra as an undergraduate (or just a short course) you should also consider M560.

Relevant topics courses, offered if there is sufficient student interest (M676), include Computational Group theory, Computer Algebra and Algebraic Number Theory.

Prospective Students: If you are not yet a student at Colorado State University you can find information about our programs on the departmental web pages.

Many projects involve explicit computation. For these, basic knowledge of some programming language is helpful, but is not a prerequisite.

Potential Projects: I maintain a list of GAP-related thesis and project topics, but this is not considered exclusive.

Information Technology Aspects

While the development of algorithms for groups is the majority of mathematical work (and requires knowledge of graduate level mathematics), the fact that algorithms end up in a distributed system provides a series of challenges that are much closer to computer science and engineering:

• Usability for Mathematicians is the main objective. Purely theoretical concepts are of secondary relevance.
• Having a system is of substantial advantage over a collection of programs. More complicated algorithms only can be built (or even conceived of) if sufficient basic routines are available and usable.
• Usability implies reasonable performance. This means that algorithms do not only have to be theoretically good (complexity) but also fast in practice.
  A typical example is matrix multiplication over finite fields: For small dimensions the naive O(n³) algorithm performs much better than for example SCHÖNHAGE's O(n^2.7) algorithm. The break even point seems to be around dimension 1000 over small finite fields. The (even better) algorithm by COOPERSTEIN with complexity O(n^2.3) is not used in practice.
• Operations should incorporate knowledge about all arguments to use the best algorithm possible. This rules out a simple object oriented approach, the approach used could be called “operation oriented”.
• The type system should represent Mathematical knowledge. This means that an objects type can change over its life time to incorporate information that has been found out over time.
• While the language is interpreted, the implementation of fundamental routines in the system's kernel (in C) gives the convenience of an interpreted language (important for complicated mathematical algorithms) while still preserving much of the speed of a compiled language (“90% or the runtime is spent in 10% of the code'”).
• After years of speed increase with processors, algebraic and combinatorial algorithms now seriously hit the “bandwidth wall”: Issues such as cache access will have to be incorporated into core routines.
• Randomized algorithms might be faster, but care has to be taken of to verify the result. Results obtained with the system should have the same level of confidence as a refereed and published mathematical proof.
• There is strong demand for better support under Windows and better user interfaces. This however is not feasible as part of mathematical research. (We are currently exploring other funding sources.)