Fast discrete convolution in $\mathbb{R}^2$ using Sparse Bessel Decomposition
This work provides an efficient algorithm for 2D boundary integral equation solvers, which is incremental as it extends an existing 3D method to 2D.
The authors extend the Sparse Cardinal Sine Decomposition algorithm from 3D to 2D for fast computation of matrix-vector products in boundary integral equations, achieving compression and efficient computation for systems up to N=10^7.
We describe an efficient algorithm for computing the matrix vector products that appear in the numerical resolution of boundary integral equations in 2 space dimension. This work is an extension of the so-called Sparse Cardinal Sine Decomposition algorithm by Alouges et al., which is restricted to three-dimensional setups. Although the approach is similar, significant differences appear throughout the analysis of the method. Bessel decomposition, in particular, yield longer series for the same accuracy. We propose a careful study of the method that leads to a precise estimation of the complexity in terms of the number of points and chosen accuracy. We also provide numerical tests to demonstrate the efficiency of this approach. We give the compression performance for a $N \times N$ linear system for several values $N$ up to $10^7$ and report the computation time for the off-line and on-line parts of our algorithm. We also include a toy application to sound canceling to further illustrate the efficiency of our method.