Directional H^2-matrix compression for high-frequency problems.

DOI10.1002/NLA.2112MaRDI QIDQ4599029zbMATH OpenOpenAlexFDO

Authors Steffen Börm

Publication date 15 December 2017

Published in Numerical Linear Algebra with Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.07087

zbMATH Keywords

data-sparse approximationHelmholtz equationhierarchical matriceshigh-frequency problemsmatrix compression

Mathematics Subject Classification ID

Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: Standard numerical algorithms like the fast multipole method or $mathcalH$-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 directional $mathcal{H}^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 $mathcal{H}^2$-matrix using a prescribed block tree. The algorithm can reach any given accuracy, and the approximation requires only $mathcalO(nk+kapp{a}^2{k}^{2}logn)$ units of storage, where $n$ is the matrix dimension, $kappa$ is the wave number, and $k$ is the local rank. In particular, we have a complexity of $mathcalO(nk)$ if $kappa$ is constant and $mathcalO(n{k}^{2}logn)$ for high-frequency problems characterized by $kapp{a}^{2}simn$. Since the algorithm can be applied to arbitrary matrices, it can serve as the foundation of fast techniques for constructing preconditioners.

Recommendations

• Hybrid matrix compression for high-frequency problems
• Adaptive directional compression of high-frequency Helmholtz boundary element matrices
• Hierarchical matrix techniques for low- and high-frequency Helmholtz problems
• Construction of data-sparse \(\mathcal{H}^2\)-matrices by hierarchical compression
• Variable order, directional \(\mathcal{H}^2\)-matrices for Helmholtz problems with complex frequency

Cited in

(22)

• Improvement of hierarchical matrices for 3D elastodynamic problems with a complex wavenumber
• ``Interpolated factored Green function method for accelerated solution of scattering problems
• Complexity analysis of a fast directional matrix-vector multiplication
• Adaptive directional compression of high-frequency Helmholtz boundary element matrices
• Approximation of the high-frequency Helmholtz kernel by nested directional interpolation: error analysis
• Massively parallelized interpolated factored Green function method
• Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
• A new directional algebraic fast multipole method based iterative solver for the Lippmann-Schwinger equation accelerated with HODLR preconditioner
• Variable order, directional \(\mathcal{H}^2\)-matrices for Helmholtz problems with complex frequency
• Directional \(\mathcal{H}^2\) Compression algorithm: optimisations and application to a discontinuous Galerkin BEM for the Helmholtz equation
• Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs
• Hybrid matrix compression for high-frequency problems
• Sparse approximate multifrontal factorization with butterfly compression for high-frequency wave equations
• Interpolative decomposition via proxy points for kernel matrices
• A Directional Equispaced Interpolation-Based Fast Multipole Method for Oscillatory Kernels
• FMM-LU: A Fast Direct Solver for Multiscale Boundary Integral Equations in Three Dimensions
• An explicitly-sparse representation for oscillatory kernels with wave atom-like functions
• Scalable Physics-Based Maximum Likelihood Estimation Using Hierarchical Matrices
• Uniform \(\mathcal{H}\)-matrix compression with applications to boundary integral equations
• Fluid flow simulation with an \(\mathcal{H}^2\)-accelerated boundary-domain integral method
• Coupled boundary and volume integral equations for electromagnetic scattering
• A pure source transfer domain decomposition method for Helmholtz equations in unbounded domain

This page was built for publication: Directional \(\mathcal{H}^2\)-matrix compression for high-frequency problems.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4599029)