Computational Mathematics Colloquium | Deterministic computation of the characteristic polynomial in the time of matrix multiplication

Thursday, November 25, 2021 3:30 pm - 3:30 pm EST (GMT -05:00)

Speaker

Vincent Neiger | Sorbonne University
https://vincent.neiger.science/

Title

Deterministic computation of the characteristic polynomial in the time of matrix multiplication

Abstract

This talk describes joint work with Clément Pernet on an algorithm which computes the characteristic polynomial of a matrix over a field within the same asymptotic complexity, up to constant factors, as the multiplication of two square matrices. Previously, this was only achieved by resorting to genericity assumptions or randomization techniques, while the best known complexity bound with a general deterministic algorithm was obtained by Keller-Gehrig in 1985 and involves logarithmic factors. The new algorithm computes more generally the determinant of a univariate polynomial matrix in reduced form.

Remote video URL