Fast algebraic multigrid for block-structured dense systems arising from nonlocal diffusion problems

Abstract Algebraic multigrid (AMG) is one of the most efficient iterative methods for solving large structured systems of equations. However, how to build/check restriction and prolongation operators in practical AMG methods for nonsymmetric structured systems is still an interesting open question in its full generality. The present paper deals with the block-structured dense and Toeplitz-like-plus-cross systems, including nonsymmetric indefinite and symmetric positive definite (SPD) ones, arising from nonlocal diffusion problems. The simple (traditional) restriction operator and prolongation operator are employed in order to handle such block-structured dense and Toeplitz-like-plus-cross systems, which are convenient and efficient when employing a fast AMG. We provide a detailed proof of the two-grid convergence of the method for the considered SPD structures. The numerical experiments are performed in order to verify the convergence with a computational cost of only $$\mathscr {O}(N \text{ log } N)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>N</mml:mi> <mml:mspace/> <mml:mtext>log</mml:mtext> <mml:mspace/> <mml:mi>N</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> arithmetic operations, by exploiting the fast Fourier transform, where N is the number of the grid points. To the best of our knowledge, this is the first contribution regarding Toeplitz-like-plus-cross linear systems solved by means of a fast AMG.