General  Information
Important Dates
Conference Poster
Organizing Committee
Program and Schedule
Invited Talks
Contributed Talks
Software Exhibitions
Registered Participants
 Call  For
Research Papers
Software Exhibitions
Jenks Prize Nominations
 Local  Information
Conference Location
Speakers' Information
Gastronomic Guide
Additional Information
Social Events
Previous ISSACs
Other Events



Smith normal form of dense integer matrices, fast algorithms into practice

B. Saunders, Z. Wan


We present a variation of the fast Monte Carlo algorithm of Eberly, Giesbrecht and Villard for computing the Smith Form of an integer matrix. It is faster, but with the same asymptotic complexity, and it handles the singular case. Then we will apply the key principle to improve Storjohann's algorithm and Iliopoulos' algorithm. We have a near linear time algorithm for the special case of a diagonal matrix. Also, a Local Smith Form Algorithm is also considered.

We offer analysis and experimental results regarding these algorithms, with a view to the construction of an adaptive algorithm exploiting each algorithm at it's best range of performance. Finally, based on this information, we sketch the proposed structure of an adaptive Smith normal form algorithm for matrices over the integers. Our experiments use implementations in LinBox, a library available at

  issac2004 @