10:00am - 12:00pmComputational aspects of finite groups and their representations
Chair(s): Armin Jamshidpey (University of Waterloo, Canada), Eric Schost (University of Waterloo, Canada), Mark Giesbrecht (University of Waterloo, Canada)
The theory of finite groups and their representations is not only an interesting topic for mathematicians but also provides powerful tools in solving problems in science. New computational tools are making this even more feasible. To name a few, one may find applications in physics, coding theory and cryptography. On the other hand representation theory is useful in different areas of mathematics such as algebraic geometry and algebraic topology. Due to this wide range of applications, new algorithmic methods are being developed to study finite groups and their representations from a computational perspective.
Recent developments in computer algebra systems and more specifically computational linear algebra, provide tools for developments in computational aspects of finite groups and their representations. The aim of this minisymposium is to gather experts in the area to discuss the recent achievements and potential new directions.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
Construction and enumeration of finite groups
Bettina Eick
Technische Universität Braunschweig
The talk gives a short survey on the state-of-the-art of computational methods to construct or to enumerate finite groups of a given order.
Linear Time Fourier Transforms of $S_{n-k}$-invariant Functions on the Symmetric Group $S_n$
Michael Clausen
University of Bonn
Motivated by Kondor's spectral approach to the NP-complete quadratic assignment problem, this talk discusses new techniques for the efficient computation of discrete Fourier transforms (DFTs) of Sn-k-invariant functions on the symmetric group Sn. We uncover diamond- and leaf-rake-like structures in Young's seminormal and orthogonal representations leading to relatively expensive diamond and cheaper leaf-rake computations. These local computations constitute the basis of a reduction/induction process. We introduce a new anticipation technique that avoids diamond computations at the expense of only a small arithmetic overhead for leaf-rake computations. This results in local fast Fourier transforms (FFTs). Combining these local FFTs with a multiresolution scheme closely related to the inductive version of Young's branching rule we obtain a global FFT algorithm that computes the DFT of Sn-k-invariant functions on Sn in linear time. More precisely, we show that for fixed k and all n ≥ 2k DFTs of Sn-k-invariant functions on Sn can be computed in at most ck·[Sn:Sn-k] scalar multiplications and additions, where ck denotes a positive constant depending only on k. This run-time is order-optimal and improves Maslen's algorithm.
Quadratic Probabilistic Algorithms for Normal Bases
Armin Jamshidpey
University of Waterloo
It is well known that for any finite Galois extension field K/F, with Galois group G = Gal(K/F), there exists an element α in K whose orbit G·α forms an F-basis of K. Such an element α is called normal and G·α is called a normal basis. In this talk we introduce a probabilistic algorithm for finding a normal element when G is either a finite abelian or a metacyclic group. The algorithm is based on the fact that deciding whether a random element α in K is normal can be reduced to deciding whether Σσ in G σ(α)σ in K[G] is invertible. In an algebraic model, the cost of our algorithm is quadratic in the size of G for metacyclic G and slightly subquadratic for abelian G.
This is a joint work with Mark Giesbrecht (UWaterloo) and Eric Schost (UWaterloo).
