computing hermite forms of polynomial matrices
This paper presents a new algorithm for computing the Hermite form of a polynomial matrix. Given a nonsingular n x n matrix A filled with degree d polynomials with coefficients from a field, the algorithm computes the Hermite form of A using an expected number of ( n 3 d ) 1+o(1) field operations. This is the first algorithm that is both softly linear in the degree d and softly cubic in the dimension n . The algorithm is randomized of the Las Vegas type.
hermite form polynomial matrices