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

 

Le Mercredi 21 Juin 2006 à 9h45 en Salle 1 - Tour IRMA

 

Séminaire de Mr

 

Solving sparse integer linear systems

 

Résumé:

 

Recent implementations of algorithms for integer linear system solving can compute solutions of systems with around 2,000 equations over word
size numbers in about a minute. These performances are achieved for dense matrices using the highly optimized BLAS library.
We exploit the same approach to provide practical implementations for large sparse systems.
In particular, we propose a new algorithm based on a p-adic lifting technique combined with structured matrices, which reduces much of the computation to level 2 and 3 BLAS. This algorithm also achieves the first sub-cubic bit complexity for this problem according to a conjecture on certain sparse block projections.
In our talk, we will present this algorithm and emphasizes its practical benefits over the previous state of the art through our implementations in the LinBox library.