Minimisation des commmunications lors de factorisations incomplètes et d'approximations de rang faible dans le contexte des grands supercalculateurs

The impact of the communication on the performance of numerical algorithms increases with the number of cores. In the context of sparse linear systems of equations, solving Ax = b on a very large computer with thousands of nodes requires the minimization of the communication to achieve very high efficiency as well as low energy cost. The high level of sequentiality in the Incomplete LU factorization (ILU) makes it difficult to parallelize. We first introduce in this manuscript a Communication-Avoiding ILU preconditioner, denoted CA-ILU(k), that factors A in parallel and then is applied at each iteration of a solver as GMRES, both steps without communication. Considering a row block of A, the key idea is to gather all the required dependencies of the block so that the factorization and the application can be done without communication. Experiments show that CA-ILU(k) preconditioner can be competitive with respect to Block Jacobi and Restricted Additive Schwarz preconditioners. We then present a low-rank algorithm named LU factorization with Column Row Tournament Pivoting (LU-CRTP). This algorithm uses a tournament pivoting strategy to select a subset of columns of A that are used to compute the block LU factorization of the permuted A as well as a good approximation of the singular values of A. Extensive parallel and sequential tests show that LU-CRTP approximates the singular values with an error close to that of the Rank Revealing QR factorization (RRQR), while the memory storage of the factors in LU-CRTP is up to 200 times lower than of the factors in RRQR. In this context, we propose an improvement of the tournament pivoting strategy that tends to reduce the number of Flops performed as well as the communication. A column of A is discarded when this column is a linear combination of other columns of A, with respect to a threshold τ . Extensive experiments show that this modification does not degrade by much the accuracy of LU-CRTP. Moreover, compared to the Communication-Avoiding variant of RRQR, our modification reduces the number of operations by a factor of up to 36.L’impact des communications sur les performances d’un code d’algèbre linéaire augmente avec le nombre de processeurs. Dans le contexte de la résolution de systèmes d’équations linéaires creux, la résolution de Ax = b, sur une machine composée de milliers de nœuds, nécessite la minimisation des communications dans le but d’atteindre une grande efficacité tant en terme de calcul qu’en terme d’énergie consommée. La factorisation LU, même incomplète, de la matrice A est connue pour être difficilement parallélisable. Ce manuscrit présente CA-ILU(k), un nouveau préconditionneur qui minimise les communications autant durant la phase de factorisation que durant son application à chaque itération d’un solveur tel que GMRES. L’idée est de considérer un sous-ensemble de lignes de A et de lui adjoindre des données de A tel que la factorisation du sous-ensemble, ainsi que l’application des facteurs obtenus, se fait sans communication. Les expériences réalisées montre que CA-ILU(k) rivalise avec les préconditionneurs Block Jacobi et Restricted Additive Schwarz en terme d’itérations. Nous présentons ensuite un algorithme de rang faible appelé la factorisation LU couplée à une permutation des lignes et des colonnes, LU-CRTP. Cet algorithme utilise une méthode par tournoi pour sélectionner un sous-ensemble de colonnes de A, permettant la factorisation par bloc de la matrice A permutée, ainsi qu’une approximation des valeurs singulières de A. Les test séquentiels puis parallèles ont permit de mettre en évidence que LU-CRTP retourne une approximation des valeurs singulières avec une erreur proche de celle obtenue par la factorisation QR révélant le rang de la matrice (RRQR). En outre, l’espace mémoire occupé par les facteurs de LU-CRTP est jusqu’à 200 fois plus faible que dans le cas de RRQR. Toujours dans le cadre d’une approximation de rang faible, nous proposons enfin une amélioration de la stratégie de pivotage par tournoi qui réduit le nombre d’opérations effectuées ainsi que les communications. Une colonne de A est retirée de la méthode si elle est une combinaison linéaire des autres colonnes de A, suivant un critère τ . Des tests sur un grand nombre de matrices montrent que cette modification ne dégrade pas significativement la précision de LU-CRTP. En outre, cette modification appliquée à la variante de RRQR minimisant les communications réduit par un facteur de 36 le nombre d’opérations