Fast computation of the Smith form of a sparse integer matrix

DOI10.1007/PL00001611MaRDI QIDQ5957090zbMATH OpenOpenAlexFDO

Authors Mark 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

asymptotically fast algorithmdense matricesmatrix-vector productsMonte Carlo methodprobabilistic algorithmSmith normal formsparse integer matrix

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1113837
• Integer Smith form via the valence: experience with large sparse matrices from homology
• scientific article; zbMATH DE number 1254241
• A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix
• Smith normal form of dense integer matrices fast algorithms into practice

Cited in

(18)

• 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
• The shifted number system for fast linear algebra on integer matrices
• Matrices with two nonzero entries per row
• Computing the invariant structure of integer matrices: fast algorithms into practice
• Integer Smith form via the valence: experience with large sparse matrices from homology
• scientific article; zbMATH DE number 1254241 (Why is no real title available?)
• scientific article; zbMATH DE number 1254302 (Why is no real title available?)
• scientific article; zbMATH DE number 1263431 (Why is no real title available?)
• scientific article; zbMATH DE number 1113837 (Why is no real title available?)
• Smith normal form of dense integer matrices fast algorithms into practice
• Fast computation of Smith forms of sparse matrices over local rings
• Faster inversion and other black box matrix computations using efficient block projections
• Mr. Smith goes to Las Vegas: randomized parallel computation of the Smith normal form of polynomial matrices
• On efficient sparse integer matrix Smith normal form computations
• Hardness of embedding simplicial complexes in R^d
• A fast Las Vegas algorithm for computing the Smith normal form of a polynomial matrix

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5957090)