2012/01/25 by Mustafa Elsheikh, Elsheikh, Mustafa, Mark Giesbrecht +5
Computer Science · Mathematics · #Coding theory and cryptography #Commutative Algebra (math.AC) #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #FOS: Mathematics #G.4 #I.1.4 #Matrix Theory and Algorithms #Symbolic Computation (cs.SC) #cs.SC #math.AC
paper · pdf · doi:10.48550/arxiv.1201.5365
Preliminary version to appear at ISSAC 2012
openalex publication_date 2012/01/25 · arxiv created 2012/04/28 · arxiv updated 2012/05/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present algorithms to compute the Smith Normal Form of matrices over two families of local rings. The algorithms use the black-box model which is suitable for sparse and structured matrices. The algorithms depend on a number of tools, such as matrix rank computation over finite fields, for which the best-known time- and memory-efficient algorithms are probabilistic. For an \nxn matrix A over the ring \Fzfe, where fe is a power of an irreducible polynomial f ∈ \Fz of degree d, our algorithm requires \bigO(ηde2n) operations in \F, where our black-box is assumed to require \bigO(η) operations in \F to compute a matrix-vector product by a vector over \Fzfe (and η is assumed greater than \Pden). The algorithm only requires additional storage for \bigO(\Pden) elements of \F. In particular, if η=\softO(\Pden), then our algorithm requires only \softO(n2d2e3) operations in \F, which is an improvement on known dense methods for small d and e. For the ring \ZZ/pe\ZZ, where p is a prime, we give an algorithm which is time- and memory-efficient when the number of nontrivial invariant factors is small. We describe a method for dimension reduction while preserving the invariant factors. The time complexity is essentially linear in μn r e log p, where μ is the number of operations in \ZZ/p\ZZ to evaluate the black-box (assumed greater than n) and r is the total number of non-zero invariant factors. To avoid the practical cost of conditioning, we give a Monte Carlo certificate, which at low cost, provides either a high probability of success or a proof of failure. The quest for a time- and memory-efficient solution without restrictions on the number of nontrivial invariant factors remains open. We offer a conjecture which may contribute toward that end.