Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

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.

Received:
May 6, 2005
Published:
May 6, 2005
MSC Codes:
65F05, 68P05
Keywords:
data-sparse approximation, hierarchical matrices, nested bases

Related publications

inJournal
2007 Repository Open Access
Steffen Börm

Data-sparse approximation of non-local operators by \(\mathscr {H}^2\)-matrices

In: Linear algebra and its applications, 422 (2007) 2/3, pp. 380-403