Block Low-rank Algebraic Clustering for Sparse Direct Solvers

In this talk, we adress the Block Low-Rank (BLR) clustering problem, to cluster unknowns within separators appearing during the factorization of sparse matrices. We show that methods considering only intra-separators connectivity (i.e., k-way or recursive bissection) as well as methods managing only interaction between separators have some limitations. The new strategy we propose consider interactions between a separator and its children to pre-select some interactions while reducing the number of off-diagonal blocks. We demonstrate how this method enhance the BLR strategies in the sparse direct supernodal solver PaStiX, and discuss how it can be extended to low-rank formats with more than one level of hierarchy.

Conference paper