Fast computation of normal forms of polynomial matrices

In this talk, we present recent results about fast algorithms for fundamental operations for matrices over K[X] (univariate polynomials). We mainly focus on the computation of normal forms, obtained by transforming the input matrix via elementary row operations. Depending on a degree measure specified by a "shift", these normal forms range from the Hermite form, which is triangular, to the Popov form, which minimizes the degrees of the rows.

For Popov or Hermite forms of m x m nonsingular matrices with entries of degree < d, the previous fastest algorithms use O~(m^w d) operations, where w is the exponent of K-linear algebra. We will discuss improvements in three directions:
(1) improving the cost bound to O~(m^w D/m), where D/m is a type of average degree of the input matrix; 
(2) derandomizing Hermite form computation [*]; 
(3) achieving fast computation for arbitrary shifts. 
The last point will lead us to consider the problem of solving systems of linear modular equations over K[X], which generalizes Hermite-Pade approximation and rational reconstruction.

[*] joint work with George Labahn and Wei Zhou (U. Waterloo, ON, Canada).