  A Las Vegas randomized algorithm is given to compute the Smith multipliers
for a nonsingular integer matrix $A$, that is, unimodular matrices $U$ and $V$
such that $AV=US$, with $S$ the Smith normal form of $A$. The expected running
time of the algorithm is about the same as required to multiply together two
matrices of the same dimension and size of entries as $A$. Explicit bounds are
given for the size of the entries in both unimodular multipliers. The main tool
used by the algorithm is the Smith massager, a relaxed version of $V$, the
unimodular matrix specifying the column operations of the Smith computation.
From the perspective of efficiency, the main tools used are fast linear solving
and partial linearization of integer matrices. As an application of the Smith
with multipliers algorithm, a fast algorithm is given to find the fractional
part of the inverse of the input matrix.
