The minimal basis of a univariate polynomial matrix $M(s)\in K[s]^{m\times n}$ is a basis of the syzygies of the polynomial matrix $M(s)$ with lowest possible degree, where $K[s]$ is the univariate polynomial ring over the field of $K$. It provides an efficient tool to compute the moving planes and moving quadratics of a rational parametric surface, which are employed to implicitize the parametric surface as a powerful implicitization method. In this paper, we develop two improved algorithms for computing the minimal bases of polynomial matrices. The algorithms are based on efficient methods to reduce the degrees of a set of univariate polynomial vectors. It is shown that the computational complexities of the two algorithms are $\mathcal{O}(m^{2}n^{3}d^2+d^2n^5-(2mn^4d^2-\frac{1}{6}m^3nd))$, and $\mathcal{O}(m^2nd^2+(n-m)n^3d^2+\frac{m^2n^2d^2}{n-m})$ respectively, where $m,n$ are the sizes of the polynomial matrix $M(s)$ and $d$ is the degree of each entry of the matrix. The new algorithms are faster than the state-of-the-art methods by experimental examples. Some properties about the degree of the minimal basis are also provided.