Show simple item record

dc.contributor.authorStruble, Craig Andrewen_US
dc.date.accessioned2014-03-14T20:11:08Z
dc.date.available2014-03-14T20:11:08Z
dc.date.issued2000-04-24en_US
dc.identifier.otheretd-04282000-13520019en_US
dc.identifier.urihttp://hdl.handle.net/10919/27393
dc.description.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.

en_US
dc.publisherVirginia Techen_US
dc.relation.haspartdissertation.pdfen_US
dc.rightsI hereby grant to Virginia Tech or its agents the right to archive and to make available my thesis or dissertation in whole or in part in the University Libraries in all forms of media, now or hereafter known. I retain all proprietary rights, such as patent rights. I also retain the right to use in future works (such as articles or books) all or part of this thesis or dissertation.en_US
dc.subjectcomputer algebraen_US
dc.titleAnalysis and Implementation of Algorithms for Noncommutative Algebraen_US
dc.typeDissertationen_US
dc.contributor.departmentComputer Scienceen_US
dc.description.degreePh. D.en_US
thesis.degree.namePh. D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineComputer Scienceen_US
dc.contributor.committeememberAllison, Donald C. S.en_US
dc.contributor.committeememberGupta, Sanjayen_US
dc.contributor.committeememberFarkas, Daniel R.en_US
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-04282000-13520019/en_US
dc.contributor.committeecochairHeath, Lenwood S.en_US
dc.contributor.committeecochairGreen, Edward L.en_US
dc.date.sdate2000-04-28en_US
dc.date.rdate2001-04-30
dc.date.adate2000-04-30en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record