Premium
Directional H 2 ‐matrix compression for high‐frequency problems
Author(s) -
Börm Steffen
Publication year - 2017
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2112
Subject(s) - matrix (chemical analysis) , mathematics , fast multipole method , rank (graph theory) , dimension (graph theory) , algorithm , low rank approximation , sparse matrix , mathematical optimization , multipole expansion , mathematical analysis , combinatorics , physics , materials science , quantum mechanics , hankel matrix , composite material , gaussian
Summary Standard numerical algorithms, such as the fast multipole method or H ‐matrix schemes, rely on low‐rank approximations of the underlying kernel function. For high‐frequency problems, the ranks grow rapidly as the mesh is refined, and standard techniques are no longer attractive. Directional compression techniques solve this problem by using decompositions based on plane waves. Taking advantage of hierarchical relations between these waves' directions, an efficient approximation is obtained. This paper is dedicated to directionalH 2 ‐ matrices that employ local low‐rank approximations to handle directional representations efficiently. The key result is an algorithm that takes an arbitrary matrix and finds a quasi‐optimal approximation of this matrix as a directional H 2 ‐matrix using a prescribed block tree. The algorithm can reach any given accuracy, and the approximation requires only O ( n k + κ 2 k 2 l o g n ) units of storage, where n is the matrix dimension, κ is the wave number, and k is the local rank. In particular, we have a complexity of O ( n k ) if κ is constant and O ( n k 2 l o g n ) for high‐frequency problems characterized by κ 2 ∼ n . Because the algorithm can be applied to arbitrary matrices, it can serve as the foundation of fast techniques for constructing preconditioners.