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 numberof cores. In the context of sparse linear systems of equations, solving Ax = b on a very large computerwith thousands of nodes requires the minimization of the communication to achieve very high efficiencyas 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 ILUpreconditioner, denoted CA-ILU(k), that factors A in parallel and then is applied at each iteration ofa solver as GMRES, both steps without communication. Considering a row block of A, the key idea isto gather all the required dependencies of the block so that the factorization and the application can bedone without communication. Experiments show that CA-ILU(k) preconditioner can be competitive withrespect to Block Jacobi and Restricted Additive Schwarz preconditioners. We then present a low-rankalgorithm named LU factorization with Column Row Tournament Pivoting (LU-CRTP). This algorithmuses a tournament pivoting strategy to select a subset of columns of A that are used to compute theblock 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 anerror close to that of the Rank Revealing QR factorization (RRQR), while the memory storage of thefactors in LU-CRTP is up to 200 times lower than of the factors in RRQR. In this context, we propose animprovement of the tournament pivoting strategy that tends to reduce the number of Flops performed aswell as the communication. A column of A is discarded when this column is a linear combination of othercolumns of A, with respect to a threshold τ . Extensive experiments show that this modification doesnot degrade by much the accuracy of LU-CRTP. Moreover, compared to the Communication-Avoidingvariant 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 nombrede processeurs. Dans le contexte de la résolution de systèmes d’équations linéaires creux, la résolution deAx = b, sur une machine composée de milliers de noeuds, nécessite la minimisation des communicationsdans le but d’atteindre une grande efficacité tant en terme de calcul qu’en terme d’énergie consommée. Lafactorisation LU, même incomplète, de la matrice A est connue pour être difficilement parallélisable. Cemanuscrit présente CA-ILU(k), un nouveau préconditionneur qui minimise les communications autantdurant la phase de factorisation que durant son application à chaque itération d’un solveur tel queGMRES. L’idée est de considérer un sous-ensemble de lignes de A et de lui adjoindre des donnéesde A tel que la factorisation du sous-ensemble, ainsi que l’application des facteurs obtenus, se fait sanscommunication. Les expériences réalisées montre que CA-ILU(k) rivalise avec les préconditionneurs BlockJacobi et Restricted Additive Schwarz en terme d’itérations. Nous présentons ensuite un algorithmede 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 colonnesde A, permettant la factorisation par bloc de la matrice A permutée, ainsi qu’une approximation desvaleurs 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 parla factorisation QR révélant le rang de la matrice (RRQR). En outre, l’espace mémoire occupé par lesfacteurs de LU-CRTP est jusqu’à 200 fois plus faible que dans le cas de RRQR. Toujours dans le cadred’une approximation de rang faible, nous proposons enfin une amélioration de la stratégie de pivotagepar tournoi qui réduit le nombre d’opérations effectuées ainsi que les communications. Une colonnede A est retirée de la méthode si elle est une combinaison linéaire des autres colonnes de A, suivantun critère τ . Des tests sur un grand nombre de matrices montrent que cette modification ne dégradepas significativement la précision de LU-CRTP. En outre, cette modification appliquée à la variante deRRQR minimisant les communications réduit par un facteur de 36 le nombre d’opérations