Futures for Dynamic Dependencies – Parallelizing the  \(\mathcal {H}\) -LU Factorization

The LU factorization of hierarchical matrices ( \(\mathcal {H}\) -matrices) is a challenging problem for efficient parallelization, due to complex dependency patterns. Previous research suggested the usage of tasks, but existing task-based algorithms still need a preprocessing step to prepare information about the matrix structure. In consequence, this structure must not change afterwards. This paper proposes a novel algorithm that eliminates the need for preprocessing. Its core idea is usage of the future construct. A particularly expressive type of future is needed that is not yet supported by current AMT runtime systems. This paper defines the type and shows that it promotes a clear and concise way to program parallel \(\mathcal {H}\) -LU factorization.