On efficient sparse integer matrix Smith normal form computations

DOI10.1006/jsco.2001.0451zbMath1050.65044OpenAlexW2018433009MaRDI QIDQ597114

B. David Saunders, Jean-Guillaume Dumas, Gilles Villard

Publication date: 6 August 2004

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/12bfc1cd4b807509f5a3cd99049d7205f6723eaa

zbMATH Keywords

algorithmparallel computationlarge sparse matricesinteger Smith normal form

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Canonical forms, reductions, classification (15A21)

Related Items

Efficient construction of 2-chains representing a basis of \(H_{2}(\overline {\Omega }, \partial {\Omega }; \mathbb {Z})\), The homology of partial monoid actions and Petri nets, Efficient Construction of 2-Chains with a Prescribed Boundary, Hardness of embedding simplicial complexes in \(\mathbb R^d\), Coreduction homology algorithm for inclusions and persistent homology, The ultradiscrete Toda lattice and the Smith normal form of bidiagonal matrices, An algorithm for the arithmetic classification of multilattices, Cohomology of congruence subgroups of $ {SL}_4(\mathbb {Z})$. III, Computation of cubical homology, cohomology, and (co)homological operations via chain contraction, Sequential composition of linear systems' clans, Efficiently and effectively recognizing toricity of steady state varieties, Chain homotopies for object topological representations, Coreduction homology algorithm, Trade‐off between information and computability: a technique for automated topological computations, A sensitive algorithm for detecting the inequivalence of Hadamard matrices, Recursive Double-Size Fixed Precision Arithmetic, Relating \(p\)-adic eigenvalues and the local Smith normal form, Homology of cellular structures allowing multi-incidence

Uses Software

• Homology

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel algorithms for matrix normal forms
• Factoring integers with elliptic curves
• Exact solution of linear equations using p-adic expansions
• Complexes of not \(i\)-connected graphs
• Limits for the characteristic roots of a matrix. II
• Bounds for characteristic roots of matrices
• Limits for the characteristic roots of a matrix
• 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
• Integer Smith form via the valence
• Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm
• Shift Register Synthesis (Modulo m)
• Solving sparse linear equations over finite fields
• On Computing the Smith Normal Form of an Integer Matrix
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• The 𝑘^{𝑡ℎ} prime is greater than 𝑘(ln𝑘+lnln𝑘-1) for 𝑘≥2
• Chessboard Complexes and Matching Complexes
• Complexes of Directed Graphs
• Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
• Regions in the Complex Plane Containing the Eigenvalues of a Matrix