2021/11/18 by Stavros Birmpilis, Birmpilis, Stavros, George Labahn +3 · 1 citation
Computer Science · Engineering · Mathematics · #68W30 #FOS: Computer and information sciences #Matrix Theory and Algorithms #Random Matrices and Applications #Symbolic Computation (cs.SC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2111.09949
openalex publication_date 2021/11/18 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
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 AV=US, 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 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.