E-Book Overview
ABSTRACT: In every fi eld of scientifi с and industrial research, the extension of the use of computer science has resulted in an increasing need for computing power. It is thus vital to use these computing resources in parallel. In this thesis we seek to compute the canonical form of very large sparse matrices with integer coeffi cients, namely the integer Smith normal form. By 'Very large'', we mean a million indeterminates and a million equations, i.e. thousand billion of coeffi cients. Nowadays, such systems are usually not even storable. However, we are interested in systems for which many of these coeffi cients are identical; in this case we talk about sparse systems. We want to solve these systems in an exact way, i.e. we work with integers or in smaller algebraic structures where all the basic arithmetic operations are still valid, namely fi nitefi elds. The rebuilding of the whole solution from the smaller solutions is then relatively easy.
E-Book Content
INSTITUT NATIONAL POLYTECHNIQUE DE GRENOBLE THÈSE pour obtenir le titre de D OCTEUR DE L’INPG Spécialité : «M ATHÉMATIQUES A PPLIQUÉES » préparée au L ABORATOIRE I NFORMATIQUE ET D ISTRIBUTION dans le cadre de l’É COLE D OCTORALE «M ATHÉMATIQUES ET I NFORMATIQUE » présentée et soutenue publiquement par J EAN -G UILLAUME D UMAS le 20 décembre 2000 A LGORITHMES PARALLÈLES EFFICACES POUR LE CALCUL FORMEL : ALGÈBRE LINÉAIRE CREUSE ET EXTENSIONS ALGÉBRIQUES D IRECTRICE DE THÈSE Mme. Brigitte P LATEAU J URY M. Jean D ELLA D ORA, M. Mark G IESBRECHT, M. Paul Z IMMERMANN, Mme. Brigitte P LATEAU, M. Thierry G AUTIER, M. David S AUNDERS, M. Gilles V ILLARD, Président Rapporteur Rapporteur Directrice de thèse Responsable de thèse Examinateur Examinateur Table des figures . . Table de