Algorithm 767: a Fortran 77 package for column reduction of polynomial matrices

A polynomial matrix is called column reduced if its column degrees are as low as possible in some sense. Two polynomial matrices P and R are called unimodularly equivalent if there exists a unimodular polynomial matrix U such that PU 5 R. Every polynomial matrix is unimodularly equivalent to a column-reduced polynomial matrix. In this article a subroutine is described that takes a polynomial matrix P as input and yields on output a unimodular matrix U and a column-reduced matrix R such that PU 5 R; actually PU 2 R is near zero. The subroutine is based on an algorithm, described in a paper by Neven and Praagman. The subroutine has been tested with a number of examples on different computers, with comparable results. The performance of the subroutine on every example tried is satisfactory in the sense that the magnitude of the elements of the residual matrix PU 2 R is about iPi iUiEPS, where EPS is the machine precision. To obtain these results a tolerance, used to determine the rank of some (sub)matrices, has to be set properly. The influence of this tolerance on the performance of the algorithm is discussed, from which a guideline for the usage of the subroutine is derived.