Vers une factorisation symbolique hiérarchique de rang faible pour des matrices creuses

Les algorithmes hierarchiques bases sur des techniques de compression de rang faible ont re-volutionne les methodes de resolution de systemes lineaires denses a l'aube du XXIeme siecle en reduisant considerablement les couts de calcul. Toutefois, leur application au traitement de systemes lineaires creux (comportant de nombreux elements nuls), qui sont le type de pro-blemes apparaissant le plus souvent au coeur des simulations numeriques, reste aujourd'hui un challenge majeur auquel s'attellent a la fois la communaute des matrices hierarchiques et celle des matrices creuses. A cet effet, une premiere classe d'approche a ete developpee par la communaute des matrices hierarchiques pour exploiter la structure creuse des matrices. Si le point fort de ces methodes est que l'algorithme resultant reste hierarchique, celles-ci ne par-viennent pas a exploiter certains zeros comme le font naturellement les methodes classiques de factorisation de systemes lineaires creux. A l'oppose, du fait qu'une factorisation creuse peut etre vue comme une sequence de plus petites operations denses, la communaute des matrices creuses a explore cette propriete pour introduire des techniques hierarchiques au sein de ces operations elementaires. Cependant, l'algorithme resultant perd la propriete fondamentale des algorithmes hierarchiques, dans la mesure ou la hierarchie de compression est seulement locale. Dans cet article, nous introduisons un nouvel algorithme, effectuant une factorisation symbolique creuse hierarchique qui permet d'exploiter efficacement l'ensemble des zeros de la matrice creuse et de ses facteurs tout en preservant une structure hierarchique globale. Nous montrons experimentalement que cette nouvelle approche permet d'obtenir a la fois un nombre reduit d'operations (du fait de son caractere hierarchique) et un nombre d'elements non nuls aussi reduit qu'une methode creuse (grâce au recours a une factorisation symbolique).