An exact solver for simple $\mathcal{H}$-matrix systems

Abstract

Hierarchical matrices (usually abbreviated $\mathcal{H}$-matrices) are frequently used to construct preconditioners for systems of linear equations. Since it is possible to compute approximate inverses or $LU$ factorizations in $\mathcal{H}$-matrix representation using only $\mathcal{O}(n{\log }^{2}n)$ operations, these preconditioners can be very efficient. Here we consider an algorithm that allows us to solve a linear system of equations given in a simple $\mathcal{H}$-matrix format \emph{exactly} using $\mathcal{O}(n{\log }^{2}n)$ operations. The central idea of our approach is to avoid computing the inverse and instead use an efficient representation of the $LU$ factorization based on low-rank updates performed with the well-known Sherman-Morrison-Woodbury equation.