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 linalg.org.
|