Smaller and faster generators for quasi-separable matrices

English

Séminaire Modèles et Algorithmes Déterministes: CASYS

10/11/2016 - 09:30 Mr Clément Pernet Salle 106 - Batiment IMAG

The class of quasiseparable matrices is defined by the property that any submatrix entirely below or above the main diagonal has small rank. One of the motivations, is that this class includes the closure under inversion of the class of banded matrices. These also matrices arise naturally in solving PDE's for particle interaction with the fast multi-pole method, or computing generalized eigenvalues. There, structured representations and algorithms have been designed to compute with these matrices in time linear in the matrix dimension and either quadratic cubic in the quasiseparability orders. Motivated by the design of the general purpose exact linear algebra library LinBox, and by algorithmic applications in algebraic computing, we will present recent work on the use of quasiseparable matrices in computer algebra. In particular, we will show, the connection between the notion of quasiseparability and the rank profile matrix invariant, that we have introduced in 2015. It results in two new structured representations, one being a simpler variation on the hierarchically semiseparable storage, and the second one exploiting the generalized Bruhat decomposition. As a consequence, most basic operations, such as computing the quasiseparability orders, applying a
vector, a block vector, multiplying two quasiseparable matrices together, inverting a quasiseparable matrix, can be at least as fast and often faster than previous algorithms. Still some cases are not handled and we will present the remaining open problems raised by these new storages.