Theo Mary (University of Manchester)
Matrices possessing a low-rank property arise in numerous scientific applications. This property can be exploited to provide a substantial reduction of the complexity of their LU or LDLT factorization. Among the possible low-rank matrix formats, the flat Block Low-Rank (BLR) format is easy to use but achieves superlinear complexity. Alternatively, the hierarchical formats achieve linear complexity at the price of a much more complex hierarchical matrix representation. In this talk, we propose a new format based on multilevel BLR approximations. Contrarily to hierarchical matrices, the number of levels in the block hierarchy is fixed to a given constant; we prove that this provides a simple way to finely control the desired complexity of the dense multilevel BLR factorization. By striking a balance between the simplicity of the BLR format and the low complexity of the hierarchical ones, the multilevel BLR format bridges the gap between flat and hierarchical low-rank formats. The multilevel BLR format is of particular relevance in the context of sparse (e.g. multifrontal) solvers, for which it is able to trade off the optimal dense complexity of the hierarchical formats to benefit from the simplicity of the BLR format while still achieving O(n) sparse complexity.
Alfredo Buttari Jean-Yves L'Excellent Patrick R Amestoy