  We give a Las Vegas algorithm which computes the shifted Popov form of an $m
\times m$ nonsingular polynomial matrix of degree $d$ in expected
$\widetilde{\mathcal{O}}(m^\omega d)$ field operations, where $\omega$ is the
exponent of matrix multiplication and $\widetilde{\mathcal{O}}(\cdot)$
indicates that logarithmic factors are omitted. This is the first algorithm in
$\widetilde{\mathcal{O}}(m^\omega d)$ for shifted row reduction with arbitrary
shifts.
  Using partial linearization, we reduce the problem to the case $d \le \lceil
\sigma/m \rceil$ where $\sigma$ is the generic determinant bound, with $\sigma
/ m$ bounded from above by both the average row degree and the average column
degree of the matrix. The cost above becomes $\widetilde{\mathcal{O}}(m^\omega
\lceil \sigma/m \rceil)$, improving upon the cost of the fastest previously
known algorithm for row reduction, which is deterministic.
  Our algorithm first builds a system of modular equations whose solution set
is the row space of the input matrix, and then finds the basis in shifted Popov
form of this set. We give a deterministic algorithm for this second step
supporting arbitrary moduli in $\widetilde{\mathcal{O}}(m^{\omega-1} \sigma)$
field operations, where $m$ is the number of unknowns and $\sigma$ is the sum
of the degrees of the moduli. This extends previous results with the same cost
bound in the specific cases of order basis computation and M-Pad\'e
approximation, in which the moduli are products of known linear factors.
