Analysis and Implementation of Algorithms for Noncommutative Algebra

Abstract

A fundamental task of algebraists is to classify algebraic structures. For example, the classification of finite groups has been widely studied and has benefited from the use of computational tools. Advances in computer power have allowed researchers to attack problems never possible before.

In this dissertation, algorithms for <I>noncommutative</I> algebra, when <I>ab</I> is not necessarily equal to <I>ba</I>, are examined with practical implementations in mind. Different encodings of <I>associative algebras</I> and <I>modules</I> are also considered. To effectively analyze these algorithms and encodings, the <I>encoding neutral</I> analysis framework is introduced. This framework builds on the ideas used in the arithmetic complexity framework defined by Winograd. Results in this dissertation fall into three categories: analysis of algorithms, experimental results, and novel algorithms.

Known algorithms for calculating the Jacobson radical and Wedderburn decomposition of associative algebras are reviewed and analyzed. The algorithms are compared experimentally and a recommendation for algorithms to use in computer algebra systems is given based on the results.

A new algorithm for constructing the Drinfel'd double of finite dimensional Hopf algebras is presented. The performance of the algorithm is analyzed and experiments are performed to demonstrate its practicality. The performance of the algorithm is elaborated upon for the special case of group algebras and shown to be very efficient.

The <tt>MeatAxe</tt> algorithm for determining whether a module contains a proper submodule is reviewed. Implementation issues for the <tt>MeatAxe</tt> in an encoding neutral environment are discussed. A new algorithm for constructing endomorphism rings of modules defined over path algebras is presented. This algorithm is shown to have better performance than previously used algorithms.

Finally, a linear time algorithm, to determine whether a quotient of a path algebra, with a known Gr&ouml;bner basis, is finite or infinite dimensional is described. This algorithm is based on the Aho-Corasick pattern matching automata. The resulting automata is used to efficiently determine the dimension of the algebra, enumerate a basis for the algebra, and reduce elements to normal forms.