A fast, deterministic algorithm for computing a Hermite Normal Form of a polynomial matrix

2016/02/05 by Labahn, George, Zhou, Wei
#FOS: Computer and information sciences #Symbolic Computation (cs.SC)

paper · doi:10.48550/arxiv.1602.02049

Abstract

Given a square, nonsingular matrix of univariate polynomials F ∈ \mathbbK[x]^{n × n} over a field \mathbbK, we give a fast, deterministic algorithm for finding the Hermite normal form of F with complexity O^∼(n^ωd) where d is the degree of F. Here soft-O notation is Big-O with log factors removed and ω is the exponent of matrix multiplication. The method relies of a fast algorithm for determining the diagonal entries of its Hermite normal form, having as cost O^∼(n^ωs) operations with s the average of the column degrees of F.

Related

• Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix
• A Polynomial-time Algorithm to Compute Generalized Hermite Normal Form of Matrices over Z[x]
• A cubic algorithm for computing the Hermite normal form of a nonsingular integer matrix
• Computing Popov and Hermite forms of rectangular polynomial matrices
• Fast and deterministic computation of the determinant of a polynomial matrix