  We present the asymptotically fastest known algorithms for some basic
problems on univariate polynomial matrices: rank, nullspace, determinant,
generic inverse, reduced form. We show that they essentially can be reduced to
two computer algebra techniques, minimal basis computations and matrix fraction
expansion/reconstruction, and to polynomial matrix multiplication. Such
reductions eventually imply that all these problems can be solved in about the
same amount of time as polynomial matrix multiplication.
