The most efficient algorithms to solve linear systems with structures such as Toeplitz, Vandermonde or, Cauchy-likeness are randomized. Such algorithms rely on a structured version of the fast Gaussian elimination that requires the input matrix to satisfy the generic rank profile condition. When the latter is not satisfied, a randomized preprocessing step is used. In this work, we present a deterministic algorithm that solves such systems within a complexity that matches the best known bounds previously achievable only through randomization. The algorithm relies on 3 main steps, each handled using recently developed fast and deterministic algorithms for modular approximation problems. We extract a vector M-Padé approximation, compress its solutions via kernel computations, then reduce it to a simultaneous M-Padé approximation.
Localisation
Salle de séminaire 4B107 (bâtiment Copernic)
5, boulevard Descartes, 77420 Champs-sur-Marne