Optimal memory minimization algorithms for the multifrontal method

Abdou Guermouche (1, 2) , Jean-Yves L'Excellent (1, 2)

1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
2 LIP - Laboratoire de l'Informatique du Parallélisme

We are interested in the active and total memory usage of the multifrontal method. Starting from the algorithms proposed by Liu, we suggest a new scheme together with a tree traversal that give an optimal peak of active memory. Significant gains are obtained compared to Liu's approach. We also study the problem of minimizing the total memory and compare various new schemes. A number of experiments shows the interest of these approaches.

Nous nous intéressons à l’optimisation mémoire pour l’approche multi-frontale. Repartant des algorithmes proposés par Liu, nous proposons de nouveaux algorithmes et parcours d’arbre visant à minimiser la mémoire. Dans le cas out-of-core nous proposons un algorithme optimal pour la taille de la mémoire active, alors que pour le cadre in-core nous nous intéressons à la minimisation de la mémoire totale et proposons plusieurs nouvelles approches. Cette étude théorique est complétée par des expérimentations sur un grand nombre de problèmes tests qui montrent les améliorations obtenues

Mots clés: MULTIFRONTAL METHOD; SPARSE MATRICES; MEMORY; TREE TRAVERSAL; LIU'S ALGORITHM

Mots clés: ALGORITHME DE LIU; METHODE MULTIFRONTALE; MATRICES CREUSES; MEMOIRE; PARCOURS D'ARBRE

Domaines: Autre [cs.OH]

Abdou Guermouche, Jean-Yves L'Excellent. Optimal memory minimization algorithms for the multifrontal method. [Research Report] RR-5179, LIP RR-2204-26, INRIA, LIP. 2004. ⟨inria-00071409⟩