ALGORITHMS FOR COMPUTING THE HERMITE REDUCTION OF A POLYNOMIAL MATRIX

In this paper, we study some algorithms for computing an Hermite reduc tion of a matrix with polynomial entries which avoid the swell-up of t he size of intermediary objects and have a good sequential complexity. The second and the third algorithms generalize the sub-resultant meth od for computing the gcd of two polynomials. The last one is optimal i n the sense that it computes an Hermite reduction with a minimal degre e change of basis matrix. The Hermite reduction with polynomials entri es amounts to a linear algebra problem over the coefficient field with a good control of the dimensions. Our problem of linear algebra is a progressive triangulation of matrices. So it is feasible exactly when there exists a polynomial time algorithm computing determinants of mat rices with entries in the coefficient field of the polynomials given a s input. Theoretical results are better than for previously known algo rithms, and practical results are interesting.