Iliopoulos, C. S. (1983) Computational problems in the theory of Abelian groups. PhD thesis, University of Warwick.

Preview

PDF WRAP_Theses_Iliopoulos_1983.pdf - Submitted Version - Requires a PDF viewer. Download (5Mb) | Preview

Request Changes to record.

Abstract

In this thesis, the worst-case time complexity bounds on the algorithms for the problems mentioned below have been improved.

A. Algorithms on abelian groups represented by a set of defining relations for computing:

(I) a canonical basis for finite abelian groups
(II) a canonical basis for Infinite abelian group

B. Algorithms for computing:

(I) Hermite normal form of an Integer matrix
(II) The Smith normal form of an Integer matrix
(III) The set of all solutions of a system of Diophantine Equations

C. Algorithms on abelian groups represented by an explicit set of generators for computing:

(I) the order of an element (space complexity 1s only improved)
(II) a complete basis for a finite abelian group
(III) membership-Inclusion testing
(IV) the union and Intersection of two finite abelian groups

D. A classification of the relative complexity of computational problems on abelian groups (as above) factorization and primility testing.

E. Algorithms on abelian subgroups of the symmetric group for computing:

(I) the complete structure of a group
(II) membership-Indus Ion testing
(III) the union of two abelian groups
(IV) the Intersection of two abelian groups.

Item Type:	Thesis (PhD)
Subjects:	Q Science > QA Mathematics
Library of Congress Subject Headings (LCSH):	Abelian groups, Diophantine equations, Algorithms, Factorization (Mathematics)
Official Date:	1983
Dates:	Date Event 1983 UNSPECIFIED
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Thesis Type:	PhD
Publication Status:	Unpublished
Sponsors:	Alexander S. Onassis Public Benefit Foundation
Extent:	197 leaves
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads