Abstract : Matrices whose coefficients are univariate polynomials over a field are a basic mathematical object which arises at the core of fundamental algorithms in computer algebra: sparse or structured linear system solving, rational approximation or interpolation, division with remainder for bivariate polynomials, etc. After presenting this context, we will give an overview of recent progress on efficient computations with such matrices. Next, we will show how these results have been exploited to improve complexity bounds for a selection of problems which, interestingly, do not necessarily involve polynomial matrices a priori: computing the characteristic polynomial of a scalar matrix, performing modular composition of univariate polynomials, changing the monomial order for multivariate Gröbner bases.

Keywords : computer algebra; computational complexity; polynomial matrices; Hermite-Padé approximation; multivariate interpolation