On lattice reduction for polynomial matrices

Abstract

A simple algorithm for transformation to weak Popov form | essentially lattice reduction for polynomial matrices | is described and analyzed. The algorithm is adapted and applied to various tasks involving polynomial matrices: rank prole and determinant computation; unimodular triangular factorization; transformation to Hermite and Popov canonical form; rational and diophantine linear system solving; short vector computation.