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

 

Le Jeudi 16 Juin 2005 à 9h45 en Salle 1 - Tour IRMA

 

Séminaire de Mr David SAUNDERS

 

Engineered hybrid algorithms for exact linear algebra.

 

Résumé:

 

Engineered algorithms are attempts to provide, from a range of algorithm choices, the best method for the given input. The adjective "engineered" is meant to suggest that the choice may be a hybrid of several algorithms and that a healthy mix of asymptotic complexity information and consideration of problem instances previously encountered in practice will be used in determining the structure of the hybrid algorithm. We will discuss several engineered algorithms in detail. An adaptive matrix rank algorithm and a
hybrid Smith normal form are illuminating examples. A characteristic polynomial algorithm and one for symmetric matrix signature are works in progress.

The basic problems of hybrid algorithms are (1) to avoid spending too much time probing wrong algorithmic choices before finding the best approach for the problem instance at hand, and (2) maintenance: being able to adapt a hybrid to use new algorithms and to respond to new instance patterns occurring in practice. There are varied and numerous solutions to the first problem, some of which I illustrate and I try to make the point that this is a worthwhile place to exercise your algorithm design cleverness (at least in the
sparse linear algebra context). For the second problem I can offer only a melange of remarks.