Analysis and Implementation of Algorithms for Noncommutative Algebra

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ö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.

Name thesis:degree_name

Ph. D.

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

Computer Science

Department dc:contributor.department

Computer Science

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

2000

Author dc:creator

• Struble, Craig Andrew

Chairs dc:contributor.committeechair

• Heath, Lenwood S.
• Green, Edward L.

Committee members dc:contributor.committeemember

• Allison, Donald C. S.
• Gupta, Sanjay
• Farkas, Daniel R.

• computer algebra

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

etd-04282000-13520019

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/27393