Computing the Smith form with multipliers for a nonsingular integer matrix


Séminaire AMAC: CASC

8/11/2023 - 15:15 Arne Storjohann IMAG 206

Given a nonsingular integer input matrix $A$, we have recently given an algorithm that computes the Smith canonical form $S$ together with unimodular matrices $U$ and $V$ such that $A V = U S$.  The running time of the algorithm is about the same as required to multiply together two matrices of the same dimension and size of entries as $A$. In this talk, I will explain at a high level the main mathematical and computational tools that we have developed to obtain this result.