We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
44/2005
Data-sparse approximation of non-local operators by ${\mathcal H}^2$-matrices
Steffen Börm
Abstract
Many of today's most efficient numerical methods are based on multilevel decompositions: The multigrid algorithm is based on a hierarchy of grids, wavelet techniques use a hierarchy of basis functions, while fast panel-clustering and multipole methods employ a hierarchy of clusters.
The high efficiency of these methods is due to the fact that the hierarchies are nested, i.e., that the information present on a coarser level is also present on finer levels, thus allowing efficient recursive algorithms.
${\mathcal H}^2$-matrices employ nested local expansion systems in order to approximate matrices in optimal (or for some problem classes at least optimal up to logarithmic factors) order of complexity. This paper presents a criterion for the approximability of general matrices in the ${\mathcal H}^2$-matrix format and an algorithm for finding good nested expansion systems and constructing the approximation efficiently.