Uniform H-matrix Compression with Applications to Boundary Integral Equations

Boundary integral equation formulations of elliptic partial differential equations lead to dense system matrices when discretized, yet they are data-sparse. Using the H-matrix format, this sparsity is exploited to achieve O(Nlog 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 H²-matrix format improves the complexity to O(N) by introducing a recursive structure onto subblocks on multiple levels. However, in practice this comes with a large proportionality constant, making the H²-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 H-matrices. An algebraic compression algorithm is introduced to transform a regular H-matrix into a uniform H-matrix, which maintains the asymptotic complexity.