Approximation of integral operators by Green quadrature and nested cross approximation

We present a fast algorithm that constructs a data-sparse approximation of matrices arising in the context of integral equation methods for elliptic partial differential equations. The new algorithm uses Green's representation formula in combination with quadrature to obtain a first approximation of the kernel function, and then applies nested cross approximation to obtain a more efficient representation. The resulting $${\mathcal H}^2$$H2-matrix representation requires $${\mathcal O}(n k)$$O(nk) units of storage for an $$n\times n$$n×n matrix, where k depends on the prescribed accuracy.