A multigrid method for nonlocal problems: Non-diagonally dominant or toeplitz-plus-tridiagonal systems

Nonlocal problems have been used to model very different applied scientific phenomena which involve the fractional Laplacian when one looks at the L'evy processes and stochastic interfaces. This paper deals with the nonlocal problems on a bounded domain where the stiffness matrices of the resulting systems are Toeplitz plus tridiagonal or far from being diagonally dominant as occurs when dealing with linear finite element approximations. By exploiting a weakly diagonally dominant Toeplitz property of the stiffness matrices, the optimal convergence of the two-grid method is well established in [Fiorentino and Serra-Capizzano, SIAM J. Sci. Comput., 17 (1996), pp. 1068-1081; Chen and Deng, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 869-890], and there are still questions about the best ways to define the coarsening and interpolation operators when the stiffness matrix is far from being weakly diagonally dominant [St" uben, J. Comput. Appl. Math., 128 (2001), pp. 281-309]. In this work, using spectral indications from our analysis of the involved matrices, the simple (traditional) restriction operator and prolongation operator are employed in order to handle general algebraic systems which are neither Toeplitz nor weakly diagonally dominant corresponding to the fractional Laplacian kernel and the constant kernel, respectively. We focus our efforts on providing the detailed proof of the convergence of the two-grid method for such situations. Moreover, the convergence of the full multigrid is also discussed with the constant kernel. The numerical experiments are performed to verify the convergence with only scrO (NlogN) complexity by the fast Fourier transform, where N is the number of the grid points.