Résolution de systèmes linéaires dans les semi-anneaux et les dioïdes

M. Minoux

LIP6 1998/051: Rapport de Recherche LIP6 / LIP6 research reports
51 pages - Décembre/December 1998 - French document.

PostScript : 104 Ko /Kb

Contact : par mail / e-mail

Thème/Team: Algorithmique Numérique et Parallélisme

Titre français : Résolution de systèmes linéaires dans les semi-anneaux et les dioïdes
Titre anglais : Algorithms for linear systems over semi-rings and dioids

Résumé : La plupart des algorithmes classiques de résolution de systèmes linéaires dans l'algèbre usuelle peut se transposer à des structures algébriques beaucoup plus générales telles que les semi-anneaux et les dioïdes. Nous présentons ici une synthèse de ces extensions : méthode itératives de JACOBI, et de GAUSS-SEIDEL généralisées ; méthodes d'élimination de GAUSS-JORDAN et "Escalier" généralisées, algorithme "glouton" généralisé. Pour le cas particulier du problème de plus court chemin dans un graphe, on retrouve ainsi de nombreux algorithmes connus : algorithmes de FORD-BELLMANN, algorithme de FLOYD, algorithme de DANTZIG et algorithme de DIJKSTRA.

Abstract : Many classical algorithms for solving linear systems in usual algebra may be extended to much more general algebraic structures such as semi-rings and dioids. We present here a synthetic overview of these extensions : iterative methods such as generalized JACOBI and GAUSS-SEIDEL algorithms ; elimination methods such as generalized GAUSS-JORDAN and "Escalator" algorithms ; generalized "greedy" algorithm. As interesting special cases, we find again various well-known algorithms for solving the shortest path problem on directed graphs : the FORD-BELLMANN algorithm, FLOYD'S and DANTZIG's algorithm, and DIJKSTRA's algorithm.

Mots-clés : semi-anneaux, dioïdes, systèmes linéaires

Key-words : semi-rings, dioids, linear systems

Publications internes LIP6 1998 / LIP6 research reports 1998

Responsable Éditorial / Editor
webmaster@lip6.fr