# Lecture note 17/2003

## Data-Sparse Approximation of Integral Operators

### Boris N. Khoromskij

**Contact the author:** Please use for correspondence this email.**Submission date: **26. May. 2003**Pages: 63****published as: ****Khoromskij**, **B. N.**: Data-sparse approximation of integral operators

Leipzig : Max-Planck-Institut für Mathematik in den Naturwissenschaften, 2003. - 61 p.

(Lecture notes / Max Planck Institute for Mathematics in the Sciences ; 17/2003)**Bibtex****Download full preprint:** PDF (710 kB), PS ziped (310 kB)**Abstract:**

These notes are based on a lecture course given by the author in the
winter
semester of 2002-2003 for postgraduate students at the University of
Leipzig. The purpose of this course was to provide an introduction to
modern *methods of a data-sparse approximation to integral and more
general nonlocal operators* based on the use of hierarchical
matrices (or briefly -matrices).
Being
a direct descendant of well established
panel clustering, fast multipole and mosaic-skeleton methods,
the -matrix technique allows in addition matrix-matrix operations of
almost linear cost. As a consequence, it provides a constructive
tool for the efficient matrix representation
and fast matrix arithmetics
in a wide range of applications.

We focus on the error and complexity analysis of the -matrix
approximation to integral operators. To summarize briefly, a class of
operators with asymptotically smooth kernels
can be approximated up to a tolerance , ,
by data-sparse -matrix of almost linear complexity
, where *N* is the size of a discrete problem.

We begin with a short survey on the Galerkin finite element methods for strongly elliptic variational equations. Next we give an insight to the classical polynomial approximation of multivariate functions. To proceed with, we construct a hierarchical decomposition of the product integration domain that refines adaptively towards the set of singularity points of the kernel. The polynomial interpolation allows then a patch-wise degenerate approximation to the kernel function in issue. The desired data-sparse -matrix approximation comes up through the finite element Galerkin method applied to the operator with a modified kernel as above.

All in all, the -matrix format can be specified by a list of low-rank matrix blocks within a hierarchical matrix partitioning that is refined towards the main diagonal. We discuss the key building blocks in the -matrix construction and prove the linear-logarithmic costs for the memory requirements and for the matrix-by-vector product. Moreover, the matrix-matrix multiplication and the -matrix inverse can be also implemented (approximately) within the given format, and with complexity.

The basic hierarchical format can be improved and generalised in several directions as follows:

- (i)
Uniform and -matrices;

- (ii)
blended -matrix approximation;

- (iii)
coarsening of the hierarchical format using weaker admissibility criteria;

- (iv)
wire-basket approximation for -harmonic kernels;

- (v)
hierarchical approximation on graded meshes;

- (vi)
direct data-sparse representation for the Green function;

- (vii)
hierarchical Kronecker tensor-product forma