Complexity analysis of a fast directional matrix-vector multiplication

DOI10.1007/978-3-030-67077-1_3MaRDI QIDQ2233546zbMATH OpenOpenAlexFDO

Authors G. Of, Raphael Watschinger

Publication date 18 October 2021

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

zbMATH Keywords

fast multipole methodHelmholtz kernelhierarchical matrix

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20)

Abstract: We consider a fast, data-sparse directional method to realize matrix-vector products related to point evaluations of the Helmholtz kernel. The method is based on a hierarchical partitioning of the point sets and the matrix. The considered directional multi-level approximation of the Helmholtz kernel can be applied even on high-frequency levels efficiently. We provide a detailed analysis of the almost linear asymptotic complexity of the presented method. Our numerical experiments are in good agreement with the provided theory.

Recommendations

• Fast directional algorithms for the Helmholtz kernel
• Directional \(\mathcal{H}^2\)-matrix compression for high-frequency problems.
• Variable order, directional \(\mathcal{H}^2\)-matrices for Helmholtz problems with complex frequency
• Fast-multipole method: a mathematical study
• Analysis of a diagonal form of the fast multipole algorithm for scattering theory

Cites work

• A fast algorithm for particle simulations
• A wideband fast multipole method for the Helmholtz equation in three dimensions
• Adaptive low-rank approximation of collocation matrices
• Approximation of the high-frequency Helmholtz kernel by nested directional interpolation: error analysis
• Diagonal forms of translation operators for the Helmholtz equation in three dimensions
• Directional \(\mathcal{H}^2\)-matrix compression for high-frequency problems.
• Efficient fast multipole method for low-frequency scattering
• Fast Directional Multilevel Algorithms for Oscillatory Kernels
• Fast directional multilevel summation for oscillatory kernels based on Chebyshev interpolation
• Hierarchical matrices: algorithms and analysis
• Hybrid matrix compression for high-frequency problems
• Multilevel computations of integral transforms and particle interactions with oscillatory kernels
• The fast solution of boundary integral equations.
• Wideband nested cross approximation for Helmholtz problems

Cited in

(5)

• Approximation of the high-frequency Helmholtz kernel by nested directional interpolation: error analysis
• Variable order, directional \(\mathcal{H}^2\)-matrices for Helmholtz problems with complex frequency
• Performance Bounds for Complex-Valued Independent Vector Analysis
• scientific article; zbMATH DE number 7711611 (Why is no real title available?)
• Semi-analytic integration for a parallel space-time boundary element method modelling the heat equation

This page was built for publication: Complexity analysis of a fast directional matrix-vector multiplication

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