Preconditioning of linear systems for massively parallel computers (CM-2)

L’introduction des supercalculateurs parallèles a donné une nouvelle dimension au calcul scientifique. Des problèmes, qui étaient impossibles à simuler numériquement, peuvent maintenant être résolus. Mais, bien que ces machines aient de très grandes capacités de calculs (plusieurs centaines de millions d’opérations à la seconde), elles sont souvent sous-utilisées car les algorithmes de résolution ne sont pas exprimés de manière vectorielle ou ne contiennent pas assez de parallélisme. Nous nous sommes intéressés à la solution de systèmes linéaires provenant de la discrétisation par différences finies d’équations aux dérivées partielles elliptiques sur ordinateurs à architecture massivement parallèle à parallélisme sur les données. Le modèle d’une telle machine sera pour nous la Connection Machine (CM-2). Dans ce cas, la méthode du gradient conjugué (GC) semble relativement bien adaptée à la CM-2. Introduite en 19562 par Hestenes et Stiefel, cette méthode permet la résolution de systèmes linéaires Ax=b dont la matrice A est symétrique définie positive. Cependant le GC n’est pas efficace si les valeurs propres de la matrice ont des ordres de grandeurs différents. Par conséquent, nous avons utilisé la généralisation de cette méthode popularisée par Concus, Golub et O’Leary (1976) : le gradient conjugué préconditionné (GCP).Le problème crucial, que pose l’efficacité du GCP, est donc celui du préconditionnement. Le problème étudié possède des solutions efficaces comme la décomposition incomplète de Cholesky. Elles sont adaptées à une architecture vectorielle mais non massivement parallèle. Nous avons alors étudié et mis en oeuvre des préconditionnements polynomiaux et face à l’instabilité des algorithmes, nous les avons couplés avec le schéma de Horner. Nous avons ensuite testé en fonction du degré des polynômes et de la taille des matrices afin d’aboutir à une résolution la plus rapide possible (en temps CPU) de la résolution des systèmes linéaires.The introduction of parallel supercomputers has given a new dimension to scientific computing. Problems, which were impossible to simulate numerically, can now be solved. But, although these machines have very large computing capacities (several hundreds of millions of operations per second), they are often underused because the resolution algorithms are not expressed in a vectorial way or do not contain enough parallelism.We are interested in the solution of linear systems coming from the discretization by finite differences of elliptical partial differential equations on computers with massively parallel architecture with parallelism on the data. The model of such a machine for us will be the Connection Machine (CM-2). In this case, the conjugate gradient (GC) method seems relatively well suited to CM-2. Introduced in 19562 by Hestenes and Stiefel, this method allows the resolution of linear systems Ax=b whose matrix A is symmetric positive definite. However the GC is not efficient if the eigenvalues ​​of the matrix have different orders of magnitude. Therefore, we used the generalization of this method popularized by Concus, Golub and O’Leary (1976): the preconditioned conjugate gradient (PCG).The crucial problem posed by the effectiveness of the GCP is therefore that of preconditioning. The problem studied has effective solutions such as the incomplete Cholesky decomposition. They are adapted to a vector architecture but not massively parallel. We then studied and implemented polynomial preconditioning and faced with the instability of the algorithms, we coupled them with Horner's scheme. We then tested according to the degree of the polynomials and the size of the matrices in order to achieve the fastest possible resolution (in CPU time) of the resolution of the linear systems