Aurélien Falco will present us his work on hierarchical symbolic factorization for sparse matrices during the next HiePACS Working Group, on Monday (December 17th) at 13:00 in Boole 2 room.
Hierarchical Symbolic Factorization for Sparse Matrices
Hierarchical methods based on low-rank compression have drastically reduced computational requirements for the solution of dense linear systems over the last two decades. For sparse linear systems, more common in numerical simulation, their application remains a challenge which has been studied both by the community of hierarchical matrices
and the community of sparse matrices. On one hand, the first step taken by the community of hierarchical matrices most often takes advantage of the sparsity of the problem through the use of nested dissection. While this method benefits from the resulting hierarchical structure, it is not, however, as efficient as sparse solvers regarding the exploitation
of zeros and the structural separation of zeros from non-zeros. On the other hand, sparse linear systems can be decomposed as a sequence of smaller dense operations, enticing sparse solvers to use this property to borrow compression techniques from hierarchical methods to reduce the computational cost of these elementary operations. Nonetheless, the globally hierarchical structure may be lost if the compression of hierarchical methods is used only locally on dense submatrices. In this presentation, we will review the main techniques that have been employed
by both those communities, trying to highlight their shared properties and their respective limits with a special emphasis on studies that have aimed at bridging the gap between them. This review motivates the introduction of a class of hierarchical algorithms performing a symbolic factorization at different levels of the cluster (or block elimination)
tree and questions whether supernodes shall have (hierarchically) consistent data structures. Experiments with a test application (representative of Airbus’ targeted industrial application in aeroacoustics) will illustrate our discussion.