3/11/2016 - 09:30 Mr Vincent Neiger Salle 106 - Batiment IMAG
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).