Fast discrete convolution in mathbb{R}² using Sparse Bessel Decomposition

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.