## 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 *noncommutative*
algebra,
when *ab*
is not necessarily equal
to *ba*,
are examined
with practical implementations
in mind.
Different encodings
of *associative algebras*
and *modules*
are also considered.
To effectively
analyze these algorithms and encodings,
the *encoding neutral*
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 `MeatAxe` algorithm
for determining whether a module
contains a proper submodule is reviewed.
Implementation issues
for the `MeatAxe`
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ö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.

##### Collections

- Doctoral Dissertations [11232]