Computing hermite forms of polynomial matrices
Somit Gupta, Arne Storjohann · 2011
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 (n3d)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.