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
Author:
- Costas S. IliopoulosCICostas S. Iliopoulos
- 1 August 1989
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 18 (4) , 658-669
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].
Keywords
This publication has 8 references indexed in Scilit:
- Matrix multiplication via arithmetic progressions1987
- Algorithms for the Solution of Systems of Linear Diophantine EquationsSIAM Journal on Computing, 1982
- Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer MatrixSIAM Journal on Computing, 1979
- The influence of computers on algebra1974
- Schnelle Berechnung von KettenbruchentwicklungenActa Informatica, 1971
- Gaussian elimination is not optimalNumerische Mathematik, 1969
- XV. On systems of linear indeterminate equations and congruencesPhilosophical Transactions of the Royal Society of London, 1861
- Sur l'introduction des variables continues dans la théorie des nombres.Journal für die reine und angewandte Mathematik (Crelles Journal), 1851