Block Low-Rank Matrices: Main Results and Recent Advances

In many applications requiring the solution of a linear system Ax=b, the matrix A has been shown to have a low-rank property: its off-diagonal blocks have low numerical rank, i.e., they can be well approximated by matrices of small rank. Several matrix formats have been proposed to exploit this property depending on how the block partitioning of the matrix is computed.
In this talk, I will discuss the block low-rank (BLR) format, which partitions the matrix with a simple, flat 2D blocking. I will present the main characteristics of BLR matrices, in particular in terms of asymptotic complexity and parallel performance, and I will compare them to matrices based on a hierarchical block partitioning, in particular HSS matrices. I will then discuss some recent advances and ongoing research on BLR matrices: the multilevel extension of BLR matrices, the error analysis of their factorization, and finally the use of fast matrix arithmetic (e.g., Strassen's algorithm) to accelerate BLR matrix operations.