Fast Computation of Smith Forms of Sparse Matrices over Local Rings
Mark Giesbrecht (Cheriton School of Computer Science, University of Waterloo)
Monday 21 May 2012, 17.00, b-it 1.25 (cosec meeting room)
The diagonalization of matrices known as Smith Normal Form has many applications in mathematics and engineering. Computation of the Smith form of matrices over local rings, such as the integers modulo a prime power, or univariate polynomials modulo a power of an irreducible, are of particular interest. While fast algorithms for computing the Smith form of dense matrices are now well-established, exploiting sparsity in the input would allow us to address much larger problems. In this talk we present new algorithms for computing Smith forms of sparse matrices over local rings which exploit sparsity. Some of these algorithm provide provable improvements in complexity over the best previously known methods.
This is a joint work with Mustafa Elsheikh, Andy Novocin and B. David Saunders