Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Infinite Abelian Groups and Solving Systems of Linear Diophantine Equations

An $O(s^5 M(s^2 ))$ elementary operations algorithm for computing the canonical structure of infinite Abelian groups represented by a matrix of size s is presented. Also given is an algorithm for solving systems of linear Diophantine equations (say, $Ax = b$) in $O(s^{3.376} \log sM(s^2 ) + s^2 M(s^ * ))$ elementary operations, where s is the size of A and $s^ * $ is the size of b. The upper bounds mentioned above improve the results given by Chou and Collins in [SIAM J. Comput., 11 (1982), pp.687–708].