A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix. (May 2023)

• Record Type: Journal Article
• Authors: Birmpilis, Stavros; Labahn, George; Storjohann, Arne
• Is Part Of: Journal of symbolic computation. Volume 116(2023)
• Page Start: 146
• Page End: 182
• Publication Date: 2023-05
• Subjects: Smith normal form -- Unimodular matrices -- Integer matrices; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.09.002
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: A Las Vegas randomized algorithm is given to compute the Smith multipliers for a nonsingular integer matrix A, that is, unimodular matrices U and V such that A V = U S, with S the Smith normal form of A . The expected running time of the algorithm is about the same as required to multiply together two matrices of the same dimension and size of entries as A . Explicit bounds are given for the size of the entries in both unimodular multipliers. The main tool used by the algorithm is the Smith massager, a relaxed version of V, the unimodular matrix specifying the column operations of the Smith computation. From the perspective of efficiency, the main tools used are fast linear system solving and partial linearization of integer matrices. As an application of the Smith with multipliers algorithm, a fast algorithm is given to find the fractional part of the inverse of the input matrix.