Computational problems in the theory of Abelian groups
Costas S. Iliopoulos · Warwick Research Archive Portal (University of Warwick) · 1983
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.