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

DOI10.1137/0218045zbMath0689.68059OpenAlexW2015161630WikidataQ57275425 ScholiaQ57275425MaRDI QIDQ3031927

Costas S. Iliopoulos

Publication date: 1989

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0218045

zbMATH Keywords

Abelian grouptime complexityinteger matrixHermite normal formSmith normal form

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite abelian groups (20K01) Canonical forms, reductions, classification (15A21) Abelian groups (20K99)

Related Items

Faster geometric algorithms via dynamic determinant computation, Efficient construction of 2-chains representing a basis of \(H_{2}(\overline {\Omega }, \partial {\Omega }; \mathbb {Z})\), EFFICIENT ALGORITHMS FOR THE BASIS OF FINITE ABELIAN GROUPS, Computing algorithms for the reduction of a Hermite algorithm with polynomial coefficients, The determination of canonical forms for lattice quadrature rules, The number of lattice rules having given invariants, An algorithm for computing the factor ring of an ideal in Dedekind domain with finite rank, On efficient sparse integer matrix Smith normal form computations, Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix, Homology computation by reduction of chain complexes, Efficient Construction of 2-Chains with a Prescribed Boundary, Generalised cone complexes and tropical moduli in polymake, On the complexity of inverting integer and polynomial matrices, An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\)), Normal forms for general polynomial matrices, An Algorithm for Computing a Basis of a Finite Abelian Group, Computation of cubical homology, cohomology, and (co)homological operations via chain contraction, An algorithmic approach to the construction of homomorphisms induced by maps in homology, Computing Hermite and Smith normal forms of triangular integer matrices, Monte Carlo circuits for the abelian permutation group intersection problem, Toric intersection theory for affine root counting, Frontiers of sphere recognition in practice, Some speed-ups and speed limits for real algebraic geometry, Recognizing badly presented \(Z\)-modules, Index of nilpotency of binomial ideals., Parallel algorithms for matrix normal forms, Computing in general Abelian groups is hard, Computing in quotients of rings of integers