The paper “Computing Popov and Hermite forms of rectangular polynomial matrices” was accepted at the prestigious ISSAC conference earlier this year, and was recently presented at the conference in New York.
The paper is a collaboration between Johan Rosenkilde from the group, former postdoc Vincent Neiger, and former Master’s thesis student Grigory Solomatov. Parts of the results were obtained by Grigory during his Master’s thesis!
The paper concerns the computation of something similar to Gaussian elimination but for matrices with entries which are polynomials (univariate). These kind of computations were recently improved by Vincent for square matrices, but it was still open how to generalise these results to cover rectangular matrices. There are good reasons why this generalisation is not completely straightforward, and in fact most of Grigory’s thesis work was about shooting down all the obvious ways one could think of doing this.
In the end, we found a very elegant randomized algorithm, which is fast in many cases, and a more sophisticated algorithm which works well in almost all cases. The issue is not completely settled, though, and there are still a spectrum of input for which we believe a slightly faster algorithm should exist. That’s for future work!