Speaker
Theo Mary
(University of Manchester)
Description
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.
Co-authors
Alfredo Buttari
Jean-Yves L'Excellent
Patrick R Amestoy
