Efficient arithmetic operations for rank-structured matrices based on hierarchical low-rank updates

Abstract

Many matrices appearing in numerical methods for partial differential equations and integral equations are rank-structured, i.e., they contain submatrices that can be approximated by matrices of low rank. A relatively general class of rank-structured matrices are ${\mathcal {H}}^2$-matrices: they can reach the optimal order of complexity, but are still general enough for a large number of practical applications. We consider algorithms for performing algebraic operations with ${\mathcal {H}}^2$-matrices, i.e., for approximating the matrix product, inverse or factorizations in almost linear complexity. The new approach is based on local low-rank updates that can be performed in linear complexity. These updates can be combined with a recursive procedure to approximate the product of two ${\mathcal {H}}^2$-matrices, and these products can be used to approximate the matrix inverse and the LR or Cholesky factorization. Numerical experiments indicate that the new algorithm leads to preconditioners that require ${\mathcal {O}}(n)$ units of storage, can be evaluated in ${\mathcal {O}}(n)$ operations, and take ${\mathcal {O}}(n \log n)$ operations to set up.