A Fast Fourier–Galerkin Method for Solving Singular Boundary Integral Equations
Haotao Cai, Yuesheng Xu · SIAM Journal on Numerical Analysis · 2008
We propose in this paper a convenient way to compress the dense matrix representation of a compact integral operator with a smooth kernel under the Fourier basis. The compression leads to a sparse matrix with only ${\cal O}(n\log n)$ nonzero entries, where $2n$ or $2n+1$ denotes the order of the matrix. Based on this compression strategy, we develop a fast Fourier–Galerkin method for solving a class of singular boundary integral equations. We prove that the fast Fourier–Galerkin method gives the optimal convergence order ${\cal O}(n^{-t})$, where t denotes the degree of regularity of the exact solution. Moreover, we design a fast scheme for solving the corresponding truncated linear system. We show that solving this system requires only an ${\cal O}(n\log^2 n)$ number of multiplications. We present numerical examples to confirm the theoretical estimates and to demonstrate the efficiency and accuracy of the proposed algorithm.