  We present algorithms to compute the Smith Normal Form of matrices over two
families of local rings.
  The algorithms use the \emph{black-box} model which is suitable for sparse
and structured matrices. The algorithms depend on a number of tools, such as
matrix rank computation over finite fields, for which the best-known time- and
memory-efficient algorithms are probabilistic.
  For an $\nxn$ matrix $A$ over the ring $\Fzfe$, where $f^e$ is a power of an
irreducible polynomial $f \in \Fz$ of degree $d$, our algorithm requires
$\bigO(\eta de^2n)$ operations in $\F$, where our black-box is assumed to
require $\bigO(\eta)$ operations in $\F$ to compute a matrix-vector product by
a vector over $\Fzfe$ (and $\eta$ is assumed greater than $\Pden$). The
algorithm only requires additional storage for $\bigO(\Pden)$ elements of $\F$.
In particular, if $\eta=\softO(\Pden)$, then our algorithm requires only
$\softO(n^2d^2e^3)$ operations in $\F$, which is an improvement on known dense
methods for small $d$ and $e$.
  For the ring $\ZZ/p^e\ZZ$, where $p$ is a prime, we give an algorithm which
is time- and memory-efficient when the number of nontrivial invariant factors
is small. We describe a method for dimension reduction while preserving the
invariant factors. The time complexity is essentially linear in $\mu n r e \log
p,$ where $\mu$ is the number of operations in $\ZZ/p\ZZ$ to evaluate the
black-box (assumed greater than $n$) and $r$ is the total number of non-zero
invariant factors.
  To avoid the practical cost of conditioning, we give a Monte Carlo
certificate, which at low cost, provides either a high probability of success
or a proof of failure. The quest for a time- and memory-efficient solution
without restrictions on the number of nontrivial invariant factors remains
open. We offer a conjecture which may contribute toward that end.
