Computing Popov and Hermite forms of polynomial matrices
Gilles Villard · 1996
For a polynomial matrix P(z) of degree d in M~,~(K[z]) where K is a commutative field, a reduction to the Hermite normal form can be computed in O (ndM(n) + M(nd)) arithmetic operations if M(n) is the time required to multiply two n x n matrices over K. Further, a reduction can be computed using O(log~+' (ml)) pamlel arithmetic steps and O(L(nd)) processors if the same processor bound holds with time O (logX (rid)) for determining the lexicographically first maximal linearly independent subset of the set of the columns of an nd x nd matrix over K.These results are obtamed by applying in the matrix case, the techniques used in the scalar case of the gcd of polynomials.