Uniform H-matrix Compression with Applications to Boundary Integral Equations

Abstract

Boundary integral equations lead to dense system matrices when discretized, yet they are data-sparse. Using the $\mathcal{H}$-matrix format, this sparsity is exploited to achieve $\mathcal{O}(N\log N)$ complexity for storage and multiplication by a vector. This is achieved purely algebraically, based on low-rank approximations of subblocks, and hence the format is also applicable to a wider range of problems. The ${\mathcal{H}}^2$-matrix format improves the complexity to $\mathcal{O}(N)$ by introducing a recursive structure onto subblocks on multiple levels. However, in many cases this comes with a large proportionality constant, making the ${\mathcal{H}}^2$-matrix format advantageous mostly for large problems. In this paper we investigate the usefulness of a matrix format that lies in between these two: Uniform $\mathcal{H}$-matrices. An algebraic compression algorithm is introduced to transform a regular $\mathcal{H}$-matrix into a uniform $\mathcal{H}$-matrix, which maintains the asymptotic complexity. Using examples of the BEM formulation of the Helmholtz equation, we show that this scheme lowers the storage requirement and execution time of the matrix-vector product without significantly impacting the construction time.