An analysis of a butterfly algorithm

DOI10.1016/J.CAMWA.2017.05.019MaRDI QIDQ1667632zbMATH OpenOpenAlexFDO

Authors C. Börst, Steffen Börm, Jens Marcus Melenk

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) Boundary element methods for boundary value problems involving PDEs (65N38) Numerical methods for discrete and fast Fourier transforms (65T50) Complexity and performance of numerical algorithms (65Y20)

Abstract: Butterfly algorithms are an effective multilevel technique to compress discretizations of integral operators with highly oscillatory kernel functions. The particular version of the butterfly algorithm considered here realizes the transfer between levels by Chebyshev interpolation. We present a refinement of the analysis that improves the stability estimates underlying the error bounds.

Recommendations

• A parallel butterfly algorithm
• Interpolative butterfly factorization
• Fast algorithms for spherical harmonic expansions. III
• A fast butterfly algorithm for the computation of Fourier integral operators
• A stable and accurate butterfly sparse Fourier transform

Cites work

• A butterfly algorithm for synthetic aperture radar imaging
• A fast butterfly algorithm for the computation of Fourier integral operators
• A stable and accurate butterfly sparse Fourier transform
• A wideband fast multipole method for the Helmholtz equation in three dimensions
• An algorithm for the rapid evaluation of special function transforms
• Boundary element methods
• Diagonal forms of translation operators for the Helmholtz equation in three dimensions
• Efficient automatic quadrature in 3-D Galerkin BEM
• Fast Directional Multilevel Algorithms for Oscillatory Kernels
• Fast directional multilevel summation for oscillatory kernels based on Chebyshev interpolation
• scientific article; zbMATH DE number 45273 (Why is no real title available?)
• scientific article; zbMATH DE number 477682 (Why is no real title available?)
• Multidimensional butterfly factorization
• Multilevel computations of integral transforms and particle interactions with oscillatory kernels
• On the fast matrix multiplication in the boundary element method by panel clustering
• Rapid solution of integral equations of classical potential theory
• The fast multipole method: Numerical implementation
• Using NFFT 3 -- a software library for various nonequispaced fast Fourier transforms
• Wideband nested cross approximation for Helmholtz problems

Cited in

(7)

• Fast Fourier transforms of piecewise polynomials
• 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
• A butterfly algorithm for synthetic aperture radar imaging
• Wide-band butterfly network: stable and efficient inversion via multi-frequency neural networks
• A parallel butterfly algorithm
• Factorization of the Green's function of high-frequency acoustic half-space impedance problems

Describes a project that uses

Uses Software

• NFFT
• NFFT3

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

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