Algorithmes paralleles pour le calcul formel: algebre lineaire creuse et extensions algebriques

Dumas J.-G.

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.