smith normal form of dense integer matrices fast algorithms into practice
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 in practice, but with the same asymptotic complexity, and it also handles the singular case. Then we will apply the key principle to improve Storjohann's algorithm and Iliopoulos' algorithm. We have a soft linear time algorithm for the special case of a diagonal matrix. 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 form algorithm for matrices over the integers. Our experiments use implementations in LinBox, a library for exact computational linear algebra available at linalg.org.
smith normal form integer matrix