An analysis of a butterfly algorithm

DOI10.1016/j.camwa.2017.05.019zbMath1396.65171arXiv1703.01941OpenAlexW4214824508MaRDI QIDQ1667632

C. Börst, Jens Markus Melenk, Steffen Börm

Publication date: 30 August 2018

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

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

zbMATH Keywords

butterfly algorithmstability of iterated polynomial interpolation

Mathematics Subject Classification ID

Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20) Boundary element methods for boundary value problems involving PDEs (65N38)

Related Items (4)

Wide-Band Butterfly Network: Stable and Efficient Inversion Via Multi-Frequency Neural Networks ⋮ Approximation of the high-frequency Helmholtz kernel by nested directional interpolation: error analysis ⋮ \({\mathcal{H}} \)-matrix approximability of inverses of FEM matrices for the time-harmonic Maxwell equations ⋮ Fast Fourier transforms of piecewise polynomials

Uses Software

• NFFT
• NFFT3

Cites Work

• Fast directional multilevel summation for oscillatory kernels based on Chebyshev interpolation
• Rapid solution of integral equations of classical potential theory
• On the fast matrix multiplication in the boundary element method by panel clustering
• Diagonal forms of translation operators for the Helmholtz equation in three dimensions
• Multilevel computations of integral transforms and particle interactions with oscillatory kernels
• Multidimensional butterfly factorization
• Efficient automatic quadrature in 3-D Galerkin BEM
• The fast multipole method: Numerical implementation
• An algorithm for the rapid evaluation of special function transforms
• Wideband nested cross approximation for Helmholtz problems
• A wideband fast multipole method for the Helmholtz equation in three dimensions
• A Stable and Accurate Butterfly Sparse Fourier Transform
• A Butterfly Algorithm for Synthetic Aperture Radar Imaging
• Using NFFT 3---A Software Library for Various Nonequispaced Fast Fourier Transforms
• Fast Directional Multilevel Algorithms for Oscillatory Kernels
• A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators
• Boundary Element Methods
• Unnamed Item
• Unnamed Item

This page was built for publication: An analysis of a butterfly algorithm