Data-sparse approximation of non-local operators by ²-matrices

Steffen Börm

Contact the author: Please use for correspondence this email.
Submission date: 06. May. 2005 (revised version: February 2007)
Pages: 29
published in: Linear algebra and its applications, 422 (2007) 2/3, p. 380-403 
DOI number (of the published article): 10.1016/j.laa.2006.10.021
Bibtex
MSC-Numbers: 65F05, 68P05
Keywords and phrases: data-sparse approximation, hierarchical matrices, nested bases
Download full preprint: PDF (311 kB), PS ziped (244 kB)

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.

-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 -matrix format and an algorithm for finding good nested expansion systems and constructing the approximation efficiently.