Hybrid and adaptive algorithms in exact linear algebra

In recent years, considerable progress has been made in exact linearalgebra which offered us a significant number of different algorithmsfor each problem. This dissertation explores adaptive algorithms as ameans to get effective solutions. As a result, we obtain very fastsolutions in practice, the average complexity of which is comparableto the state of the art. In this thesis we consider the modeling and the use of adaptivealgorithms on the example of the computation of the integerdeterminant, of rational algorithms and of the Smith normal form. As a measure of the performance of adaptive algorithms, we propose theexpected complexity and validate our conclusions with anexperimental evaluation. To build an adaptive algorithm, we use discovered characteristics ofmatrices and the explicit comparison of partial computation times. Ouralgorithms are based on the Chinese Remaindering algorithm with fulland rational reconstruction and preconditioning. Our goal is to exploitthe early termination condition faster than other algorithms. To improve the algorithms, we can also use heuristics. In this thesiswe propose a heuristic scheme for calculating the Smith normal form ofan exact sequence of matrices. Instead of treating each matrixseparately, we show that the elimination of a row or column of matrixcauses reductions in the neighboring matrices. Thus, we succeeded incomputing some Smith forms for whole sequences, despite the fact thatit was not possible for any of the larger matrices taken separately.Ces dernières années un progrès considérable a eu lieu en algèbrelinéaire exacte qui nous offert un nombre significatif d'algorithmesdifférents pour chaque problème. Cette dissertation explore lesalgorithmes adaptatifs comme un moyen d'obtenir des solutionsefficaces. En conséquence, nous obtenons des solutions très rapides enpratique, dont la complexité moyenne est comparable à l'état del'art. Dans cette thèse nous considérons la modélisation et l'utilisationd'algorithmes adaptatifs sur l'exemple de calcul de déterminantentier, des algorithmes rationnels et du calcul de la forme normale deSmith. Comme mesure de performance des algorithmes adaptatifs, nousproposons la notation de complexité espérée et validons notreconclusions par une évaluation expérimentale. Pour construire unalgorithme adaptatif, nous utilisons des caractéristiques des matricesautomatiquement découvertes et la comparaison explicite de temps decalcul partiels. Nos algorithmes reposent sur l'algorithme de resteschinoises avec la reconstruction entière et rationnelle et sur lepréconditionnement. Notre objectif est de tirer parti la condition determinaison anticipée plus rapidement que pour les autresalgorithmes. Pour améliorer les algorithmes, nous pouvons aussi utiliser desheuristiques. Dans cette thèse nous proposons un schéma heuristiquepour le calcul de la forme de Smith d'une séquence exacte dematrices. Au lieu de traiter chaque matrice séparément, nous montronsque l'élimination d'une ligne ou d'une colonne de matrice provoque desréductions dans les matrices voisines. Ainsi, nous avons réussi àcalculer les formes de Smith pour des séquences entières, malgré lefait que ce n'était pas possible pour aucune des plus grandes matricesprises séparément