Fast computation of the Smith form of a sparse integer matrix

DOI10.1007/PL00001611zbMath0992.65039OpenAlexW2011507771MaRDI QIDQ5957090

Mark W. Giesbrecht

Publication date: 22 September 2002

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/pl00001611

zbMATH Keywords

Monte Carlo methoddense matricesprobabilistic algorithmasymptotically fast algorithmmatrix-vector productsSmith normal formsparse integer matrix

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Monte Carlo methods (65C05) Matrices of integers (15B36) Canonical forms, reductions, classification (15A21)

Related Items (5)

The shifted number system for fast linear algebra on integer matrices ⋮ Hardness of embedding simplicial complexes in \(\mathbb R^d\) ⋮ Computing the sign or the value of the determinant of an integer matrix, a complexity survey. ⋮ A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix ⋮ Relating \(p\)-adic eigenvalues and the local Smith normal form

This page was built for publication: Fast computation of the Smith form of a sparse integer matrix