Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix

Citations Over TimeTop 10% of 1989 papers

Abstract

An $O(s^5 M(s^2 ))$ algorithm for computing the canonical structure of a finite Abelian group represented by an integer matrix of size s (this is the Smith normal form of the matrix) is presented. Moreover, an $O(s^3 M(s^2 ))$ algorithm for computing the Hermite normal form of an integer matrix of size s is given. The upper bounds derived on the computational complexity of the algorithms above improve the upper bounds given by Kannan and Bachem in [SIAM J. Comput., 8 (1979), pp. 499–507] and Chou and Collins in [SIAM J. Comput., 11 (1982), pp. 687–708].

Related Papers

• → On Short Zero-Sum Subsequences of Zero-Sum Sequences(2012)6 cited
• → An Upper Bound to the Number of Conjugacy Classes of Non-Abelian Nilpotent Groups(2017)2 cited
• Basic Properties of Integer Matrix and Its Application(2010)
• Two necessary and sufficient conditions for the five-color K_4 problem(2007)
• → The Probability That an Ordered Pair of Elements is an Engel Pair(2019)