Exploitation de seconds-membres creux et multiples dans les solveurs creux directs

The cost of the solution phase in sparse direct methods is sometimes critical. Itcan be larger than the one of the factorization in applications where systems of linear equationswith thousands of right-hand sides (RHS) must be solved. In this paper, we focus on the caseof multiple sparse RHS with different nonzero structures in each column. Given a factorizationA = LU of a sparse matrix A and the system AX = B (or LY = B when focusing on the forwardelimination), the sparsity of B can be exploited in two ways. First, vertical sparsity is exploited bypruning unnecessary nodes from the elimination tree, which represents the dependencies betweencomputations in a direct method. Second, we explain how horizontal sparsity can be exploited byworking on a subset of RHS columns at each node of the tree. A combinatorial problem must thenbe solved in order to permute the columns of B and minimize the number of operations. We proposea new algorithm to build such a permutation, based on the tree and on the sparsity structure ofB. We then propose an original approach to split the columns of B into a minimal number ofblocks (to preserve flexibility in the implementation or maintain high arithmetic intensity, forexample), while reducing the number of operations down to a given threshold. Both algorithmsare motivated by geometric intuitions and designed using an algebraic approach, and they can beapplied to general systems of linear equations. We demonstrate the effectiveness of our algorithmson systems coming from real applications and compare them to other standard approaches. Finally,we give some perspectives and possible applications for this work.Le coût des résolutions triangulaires des solveurs creux directs est parfois critique.Ce coût peut dépasser celui de la factorisation dans les applications qui nécessitent la résolution deplusieurs milliers de seconds membres. Cette étude se concentre sur les cas où les seconds membressont multiples, creux et n’ont pas tous la même structure.Étant donnée la factorisation A = LU d’une matrice creuse A, l’étude met surtout l’accent sur larésolution du premier système triangulaire LY = B, où L est triangulaire inférieure. Dans ce typede problèmes, le creux dans la matrice B peut être exploité de deux manières. Premièrement, onévite le calcul de certaines lignes, ce qui correspond à élaguer certains nœuds de l’arbre d’élimination(qui représente les dépendances entre les calculs de la résolution). Deuxièmement, on réduit, pourchaque nœud, le calcul sur des sous-ensembles de colonnes de B plutôt que sur la matrice complète.Dans ce cas, un problème combinatoire doit être résolu afin de trouver une permutation des colonnesde B.S’appuyant d’abord sur l’algorithme de dissection emboîtée appliqué à un domaine régulier, unpremier algorithme est proposé pour construire une permutation des colonnes de B. Puis une nouvelleapproche permet de poursuivre la réduction du nombre d’opérations grâce à la création de blocs.Pour préserver la flexibilité de l’implémentation ainsi que l’efficacité des opérations de type BLAS 3,un nombre minimal de groupe est créé. Inspirés d’abord par des observations géométriques, ces nou-veaux algorithmes ont été étendus algébriquement pour n’utiliser que des informations provenantde la structure des seconds membres et des arbres d’élimination. Ils permettent ainsi une conver-gence rapide vers le nombre minimal d’opérations. Les résultats expérimentaux démontrent le gainobtenu par rapport à d’autres approches classiques. Enfin, les applications et extensions possiblesde ce travail sont présentées