Fast computation of Smith forms of sparse matrices over local rings
Mustafa Elsheikh, Mark W. Giesbrecht, Andy Novocin, B. David Saunders · 2012
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.