Matrix Padé Fractions and Their Computation
For matrix power series with coefficients over a field, the notion of a matrix power series remainder sequence and its corresponding cofactor sequence are introduced and developed. An algorithm for co...
For matrix power series with coefficients over a field, the notion of a matrix power series remainder sequence and its corresponding cofactor sequence are introduced and developed. An algorithm for co...
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 so...
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 so...
You are not logged in to this journal. Log in
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
SIAM J. Comput. Volume 18, Issue 4, pp. 658-669 (1989)
Issue Date: 1989
Connotea
CiteULike
del.icio.us
BibSonomy
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].
©1989 Society for Industrial and Applied Mathematics
| History: | Received 1983-12-01; accepted 1988-03-03 |
| Permalink: | http://dx.doi.org/10.1137/0218045 |
KEYWORDS and AMS
15A21, 20K01, 20K05
PUBLICATION DATA
0097-5397 (print)
1095-7111 (online)
SIAM