A New GAP Group Library for Irreducible Maximal Solvable Subgroups of Prime Degree Classical Groups

These notes are concerned with the problem of creating new group libraries for the group-theory computer system GAP (groups, algorithms, and programming). Our main objective is to develop efficient algorithms that produce a list of maximal solvable subgroups of special linear groups of prime degree over a finite field and to implement it as part of the GAP. Bibliography: 5 titles.     

Separation of Variables and the Computation of Fourier Transforms on Finite Groups,II

We present a general diagrammatic approach to the construction of efficient algorithms for computing the Fourier transform of a function on a finite group. By extending work which connects Bratteli diagrams to the construction of Fast Fourier Transform algorithms we make explicit use of the path algebra connection to the construction of Gel’fand–Tsetlin bases and work in the setting of quivers. We relate this framework to the construction of a configuration space derived from a Bratteli diagram. In this setting the complexity of an algorithm for computing a Fourier transform reduces to the calculation of the dimension of the associated configuration space. Our methods give improved upper bounds for computing the Fourier transform for the general linear groups over finite fields, the classical Weyl groups, and homogeneous spaces of finite groups, while also recovering the best known algorithms for the symmetric group.     

Multidimensional Cooley–Tukey Algorithms Revisited

The representation theory of Abelian groups is used to obtain an algebraic divide-and-conquer algorithm for computing the finite Fourier transform. The algorithm computes the Fourier transform of a finite Abelian group in terms of the Fourier transforms of an arbitrary subgroup and its quotient. From this algebraic algorithm a procedure is derived for obtaining concrete factorizations of the Fourier transform matrix in terms of smaller Fourier transform matrices, diagonal multiplications, and permutations. For cyclic groups this gives as special cases the Cooley–Tukey and Good–Thomas algorithms. For groups with several generators, the procedure gives a variety of multidimensional Cooley–Tukey type algorithms. This method of designing multidimensional fast Fourier transform algorithms gives different data flow patterns from the standard “row–column” approaches. We present some experimental evidence that suggests that in hierarchical memory environments these data flows are more efficient.     

Deciding finiteness of matrix groups in positive characteristic

We present a new algorithm to decide finiteness of matrix groups defined over a field of positive characteristic. Together with previous work for groups in zero characteristic, this provides the first complete solution of the finiteness problem for finitely generated matrix groups over a field. We also give an algorithm to compute the order of a finite matrix group over a function field of positive characteristic by constructing an isomorphic copy of the group over a finite field. Our implementations of these algorithms are publicly available in Magma.     

The Efficient Computation of Fourier Transforms on Semisimple Algebras

We present a general diagrammatic approach to the construction of efficient algorithms for computing a Fourier transform on a semisimple algebra. This extends previous work wherein we derive best estimates for the computation of a Fourier transform for a large class of finite groups. We continue to find efficiencies by exploiting a connection between Bratteli diagrams and the derived path algebra and construction of Gel’fand–Tsetlin bases. Particular results include highly efficient algorithms for the Brauer, Temperley–Lieb, and Birman–Murakami–Wenzl algebras.     

Algorithms with Adaptive Smoothing for Finite Minimax Problems

We present a new feedback precision-adjustment rule for use with a smoothing technique and standard unconstrained minimization algorithms in the solution of finite minimax problems. Initially, the feedback rule keeps a precision parameter low, but allows it to grow as the number of iterations of the resulting algorithm goes to infinity. Consequently, the ill-conditioning usually associated with large precision parameters is considerably reduced, resulting in more efficient solution of finite minimax problems.The resulting algorithms are very simple to implement, and therefore are particularly suitable for use in situations where one cannot justify the investment of time needed to retrieve a specialized minimax code, install it on one's platform, learn how to use it, and convert data from other formats. Our numerical tests show that the algorithms are robust and quite effective, and that their performance is comparable to or better than that of other algorithms available in the Matlab environment.     

Efficient computation of Fourier transforms on compact groups

This article genralizes the fast Fourier transform algorithm to the computation of Fourier transforms on compact Lie groups. The basic technique uses factorization of group elements and Gel'fand-Tsetlin bases to simplify the computations, and may be extended to treat the computation of Fourier transforms of finitely supported distributions on the group. Similar transforms may be defined on homogeneous spaces; in that case we show how special function properties of spherical functions lead to more efficient algorithms. These results may all be viewed as generalizations of the fast Fourier transform algorithms on the circle, and of recent results about Fourier transforms on finite groups. Acknowledgements and Notes. This paper was written while the author was supported by the Max-Planck-Institut für Mathematik, Bonn, Germany.     

On some computational problems in finite abelian groups

We present new algorithms for computing orders of elements, discrete logarithms, and structures of finite abelian groups. We estimate the computational complexity and storage requirements, and we explicitly determine the -constants and -constants. We implemented the algorithms for class groups of imaginary quadratic orders and present a selection of our experimental results. Our algorithms are based on a modification of Shanks' baby-step giant-step strategy, and have the advantage that their computational complexity and storage requirements are relative to the actual order, discrete logarithm, or size of the group, rather than relative to an upper bound on the group order.

     

Gaussian Groups and Garside Groups, Two Generalisations of Artin Groups

It is known that a number of algebraic properties of the braidgroups extend to arbitrary finite Coxeter-type Artin groups.Here we show how to extend the results to more general groupsthat we call Garside groups. Define a Gaussian monoid to be a finitely generated cancellativemonoid where the expressions of a given element have boundedlengths, and where left and right lowest common multiples exist.A Garside monoid is a Gaussian monoid in which the left andright lowest common multiples satisfy an additional symmetrycondition. A Gaussian group is the group of fractions of a Gaussianmonoid, and a Garside group is the group of fractions of a Garsidemonoid. Braid groups and, more generally, finite Coxeter-typeArtin groups are Garside groups. We determine algorithmic criteriain terms of presentations for recognizing Gaussian and Garsidemonoids and groups, and exhibit infinite families of such groups.We describe simple algorithms that solve the word problem ina Gaussian group, show that these algorithms have a quadraticcomplexity if the group is a Garside group, and prove that Garsidegroups have quadratic isoperimetric inequalities. We constructnormal forms for Gaussian groups, and prove that, in the caseof a Garside group, the language of normal forms is regular,symmetric, and geodesic, has the 5-fellow traveller property,and has the uniqueness property. This shows in particular thatGarside groups are geodesically fully biautomatic. Finally,we consider an automorphism of a finite Coxeter-type Artin groupderived from an automorphism of its defining Coxeter graph,and prove that the subgroup of elements fixed by this automorphismis also a finite Coxeter-type Artin group that can be explicitlydetermined. 1991 Mathematics Subject Classification: primary20F05, 20F36; secondary 20B40, 20M05.     

Automata and Square Complexes

We introduce a new geometric tool for analyzing groups of finite automata. To each finite automaton we associate a square complex. The square complex is covered by a product of two trees iff the automaton is bi-reversible. Using this method we give examples of free groups and of Kazhdan groups which are generated by the different states of one finite (bi-reversible) automaton. We also reprove the theorem of Macedońska, Nekrashevych, Sushchansky, on the connection between bi-reversible automata and the commensurator of a regular tree.     

Nonconforming finite elements and the cascadic multi-grid method

Summary. We derive sufficient conditions under which the cascadic multi-grid method applied to nonconforming finite element discretizations yields an optimal solver. Key ingredients are optimal error estimates of such discretizations, which we therefore study in detail. We derive a new, efficient modified Morley finite element method. Optimal cascadic multi-grid methods are obtained for problems of second, and using a new smoother, of fourth order as well as for the Stokes problem. Received February 12, 1998 / Revised version received January 9, 2001 / Published online September 19, 2001     

A mixed finite element approximation of the Navier-Stokes equations

Summary We study in this paper the convergence of a new mixed finite element approximation of the Navier-Stokes equations. This approximation uses low order Lagrange elements, leads to optimal order of convergence for the velocity and the pressure, and induces an efficient numerical algorithm for the solution of this problem.     

Separation of variables and the computation of Fourier transforms on finite groups, I

This paper introduces new techniques for the efficient computation of a Fourier transform on a finite group. We present a divide and conquer approach to the computation. The divide aspect uses factorizations of group elements to reduce the matrix sum of products for the Fourier transform to simpler sums of products. This is the separation of variables algorithm. The conquer aspect is the final computation of matrix products which we perform efficiently using a special form of the matrices. This form arises from the use of subgroup-adapted representations and their structure when evaluated at elements which lie in the centralizers of subgroups in a subgroup chain. We present a detailed analysis of the matrix multiplications arising in the calculation and obtain easy-to-use upper bounds for the complexity of our algorithm in terms of representation theoretic data for the group of interest.

Our algorithm encompasses many of the known examples of fast Fourier transforms. We recover the best known fast transforms for some abelian groups, the symmetric groups and their wreath products, and the classical Weyl groups. Beyond this, we obtain greatly improved upper bounds for the general linear and unitary groups over a finite field, and for the classical Chevalley groups over a finite field. We also apply these techniques to obtain analogous results for homogeneous spaces.

This is part I of a two part paper. Part II will present a refinement of these techniques which yields further savings.

     

Functional data clustering: a survey

Clustering techniques for functional data are reviewed. Four groups of clustering algorithms for functional data are proposed. The first group consists of methods working directly on the evaluation points of the curves. The second groups is defined by filtering methods which first approximate the curves into a finite basis of functions and second perform clustering using the basis expansion coefficients. The third groups is composed of methods which perform simultaneously dimensionality reduction of the curves and clustering, leading to functional representation of data depending on clusters. The last group consists of distance-based methods using clustering algorithms based on specific distances for functional data. A software review as well as an illustration of the application of these algorithms on real data are presented.     

Implementing and using high-order finite element methods

We present theoretical analyses of and detailed timings for two programs which use high-order finite element methods to solve the Navier- Strokes equations in two and three dimensions. The analyses show that algorithms popular in low-order finite element implementations are not always appropriate for high-order methods. The timings show that with the proper algorithms high-order finite element methods are viable for solving the Navier-Stokes equations. We show that it is more efficient, both in time and storage, not to precompute element matrices as the degree of approximating functions increases. We also study the cost of assembling the stiffness matrix versus directly evaluating bilinear forms in two and three dimensions. We show that it is more efficient not to assemble the full stiffness matrix for high-order methods in some cases. We consider the computational issues with regard to both Euclidean and isoparametric elements. We show that isoparametric elements may be used with higher-order elements without increasing the order of computational complexity.     

Groups with super-exponential subgroup growth

We show that, if the subgroup growth of a finitely generated (abstract or profinite) groupG is super-exponential, then every finite group occurs as a quotient of a finite index subgroup ofG. The proof involves techniques from finite permutation groups, and depends on the Classification of Finite Simple Groups.The first author was partially supported by the Hungarian National Foundation for Scientific Research, Grant No. T7441. The second author was partially supported by the Israeli National Science Foundation.     

Efficient Software-Implementation of Finite Fields with Applications to Cryptography

In this work, we present a survey of efficient techniques for software implementation of finite field arithmetic especially suitable for cryptographic applications. We discuss different algorithms for three types of finite fields and their special versions popularly used in cryptography: Binary fields, prime fields and extension fields. Implementation details of the algorithms for field addition/subtraction, field multiplication, field reduction and field inversion for each of these fields are discussed in detail. The efficiency of these different algorithms depends largely on the underlying micro-processor architecture. Therefore, a careful choice of the appropriate set of algorithms has to be made for a software implementation depending on the performance requirements and available resources.     

On nilpotent ideals in the cohomology ring of a finite group

In this paper we find upper bounds for the nilpotency degree of some ideals in the cohomology ring of a finite group by studying fixed point free actions of the group on suitable spaces. The ideals we study are the kernels of restriction maps to certain collections of proper subgroups. We recover the Quillen-Venkov lemma and the Quillen F-injectivity theorem as corollaries, and discuss some generalizations and further applications.We then consider the essential cohomology conjecture, and show that it is related to group actions on connected graphs. We discuss an obstruction for constructing a fixed point free action of a group on a connected graph with zero “k-invariant” and study the class related to this obstruction. It turns out that this class is a “universal essential class” for the group and controls many questions about the groups essential cohomology and transfers from proper subgroups.     

Topological Methods in One Numerical Scheme of Solving Three-Dimensional Continuum Mechanics Problems

We discuss numerical schemes of finite element method for solving the continuum mechanics problems. Previously a method of acceleration of calculations was developed which uses the simplicial mesh inscribed in the original cubic cell partition of a three-dimensional body. In this paper we show that the obstacle to the construction of this design may be described in terms of homology groups modulo 2. The main goal of the paper is to develop a method of removing this obstacle. The reaching of the goal is based on efficient algorithms for computing bases of the homology groups which are dual with respect to the intersection form.