Fill-in reduction in sparse matrix factorizations using hypergraphs

Oguz Kaya (1) , Enver Kayaaslan (2) , Bora Uçar (2) , Iain S. Duff (3, 4)

1 GATECH - College of Computing
2 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
3 CERFACS - Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique
4 RAL - STFC Rutherford Appleton Laboratory

We discuss the use of hypergraph partitioning based methods in fill-reducing orderings of sparse matrices for Cholesky, LU and QR factorizations. For the Cholesky factorization, we investigate a recent result on pattern-wise decomposition of sparse matrices, generalize the result, and develop algorithmic tools to obtain more effective ordering methods. The generalized results help us formulate the fill-reducing ordering problem for LU factorization as we do for the Cholesky case, without ever symmetrizing the given matrix $A$ as $|A| + |A^T|$ or $|^AT ||A|$. For the QR factorization, we adopt a recently proposed technique to use hypergraph models in a fairly standard manner. The method again does not form the possibly much denser matrix $|A^T ||A|$. We also discuss alternatives for LU and QR factorization cases where the symmetrized matrix can be used. We provide comparisons with the most common alternatives in all three cases.

Mots clés: direct methods; Fill-reducing orderings; Cholesky factorization; LU factorization; QR factorization; hypergraph partitioning; sparse matrices

Domaines: Mathématique discrète [cs.DM]; Algorithme et structure de données [cs.DS]

Oguz Kaya, Enver Kayaaslan, Bora Uçar, Iain S. Duff. Fill-in reduction in sparse matrix factorizations using hypergraphs. [Research Report] RR-8448, INRIA. 2014. ⟨hal-00932882v2⟩