On optimal tree traversals for sparse matrix factorization

Mathias Jacquelin 1, 2 Loris Marchal 1, 2 Yves Robert 1, 2 Bora Uçar 1, 2
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We study the complexity of traversing tree-shaped workflows whose tasks require large I/O files. Such workflows typically arise in the multifrontal method of sparse matrix factorization. We target a classical two-level memory system, where the main memory is faster but smaller than the secondary memory. A task in the workflow can be processed if all its predecessors have been processed, and if its input and output files fit in the currently available main memory. The amount of available memory at a given time depends upon the ordering in which the tasks are executed. What is the minimum amount of main memory, over all postorder schemes, or over all possible traversals, that is needed for an in-core execution? We establish several complexity results that answer these questions. We propose a new, polynomial time, exact algorithm which runs faster than a reference algorithm. Next, we address the setting where the required memory renders a pure in-core solution unfeasible. In this setting, we ask the following question: what is the minimum amount of I/O that must be performed between the main memory and the secondary memory? We show that this latter problem is NP-hard, and propose efficient heuristics. All algorithms and heuristics are thoroughly evaluated on assembly trees arising in the context of sparse matrix factorizations.
Type de document :
Pré-publication, Document de travail
RRLIP2010-30. 12 pages. 2013
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

Contributeur : Mathias Jacquelin <>
Soumis le : mardi 5 novembre 2013 - 17:13:59
Dernière modification le : samedi 21 avril 2018 - 01:27:14
Document(s) archivé(s) le : vendredi 7 avril 2017 - 22:01:45


Fichiers produits par l'(les) auteur(s)


  • HAL Id : ensl-00527462, version 2



Mathias Jacquelin, Loris Marchal, Yves Robert, Bora Uçar. On optimal tree traversals for sparse matrix factorization. RRLIP2010-30. 12 pages. 2013. 〈ensl-00527462v2〉



Consultations de la notice


Téléchargements de fichiers