##
**A multigrid method for nonlocal problems: non-diagonally dominant or Toeplitz-plus-tridiagonal systems.**
*(English)*
Zbl 1461.65236

Summary: Nonlocal problems have been used to model very different applied scientific phenomena which involve the fractional Laplacian when one looks at the Lévy 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 [M. Chen and W. Deng, SIAM J. Matrix Anal. Appl. 38, No. 3, 869–890 (2017; Zbl 1373.65068)], 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 [K. Stüben, J. Comput. Appl. Math. 128, No. 1–2, 281–309 (2001; Zbl 0979.65111)]. 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 \(\mathcal{O}(N\log N)\) complexity by the fast Fourier transform, where \(N\) is the number of the grid points.

### MSC:

65M55 | Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs |

26A33 | Fractional derivatives and integrals |

65T50 | Numerical methods for discrete and fast Fourier transforms |

65F05 | Direct numerical methods for linear systems and matrix inversion |

15B05 | Toeplitz, Cauchy, and related matrices |

35R11 | Fractional partial differential equations |

### Keywords:

multigrid methods; nonlocal problems; Toeplitz-plus-tridiagonal system; non-diagonally dominant system; fast Fourier transform### References:

[1] | G. Acosta and J. P. Borthagaray, A fractional Laplace equation: Regularity of solutions and finite element approximations, SIAM J. Numer. Anal., 55 (2017), pp. 472-495. · Zbl 1359.65246 |

[2] | B. Aksoylu and Z. Unlu, Conditioning analysis of nonlocal integral operators in fractional Sobolev spaces, SIAM J. Numer. Anal., 52 (2014), pp. 653-677. · Zbl 1297.65201 |

[3] | F. Andreu-Vaillo, J. M. Mazón, J. D. Rossi, and J. J. Toledo-Melero, Nonlocal Diffusion Problems, Math. Surveys Monogr. 165, AMS, Providence, RI, 2010. · Zbl 1214.45002 |

[4] | A. Aricò and M. Donatelli, A V-cycle multigrid for multilevel matrix algebras: Proof of optimality, Numer. Math., 105 (2007), pp. 511-547. · Zbl 1114.65033 |

[5] | A. Aricò, M. Donatelli, and S. Serra-Capizzano, V-cycle optimal convergence for certain (multilevel) structured linear systems, SIAM J. Matrix Anal. Appl., 26 (2004), pp. 186-214. · Zbl 1105.65322 |

[6] | R. E. Bank and C. C. Douglas, Sharp estimates for multigrid rates of convergence with general smoothing and acceleration, SIAM J. Numer. Anal., 22 (1985), pp. 617-633. · Zbl 0578.65025 |

[7] | P. Bates, On Some Nonlocal Evolution Equations Arising in Materials Science, Nonlinear Dynamics and Evolution Equations, Fields Inst. Commun., H. Brunner, X. Zhao, and X. Zou, eds., AMS, Providence, RI, 2006, pp. 13-52. · Zbl 1101.35073 |

[8] | J. Bertoin, Lévy Processes, Cambridge Tracts in Mathematics 121, Cambridge University Press, Cambridge, 1996. · Zbl 0861.60003 |

[9] | M. Bolten, M. Donatelli, T. Huckle, and C. Kravvaritis, Generalized grid transfer operators for multigrid methods applied on Toeplitz matrices, BIT, 55 (2015), pp. 341-366. · Zbl 1323.65119 |

[10] | J. H. Bramble and J. E. Pasciak, New convergence estimates for multigrid algorithms, Math. Comp., 49 (1987), pp. 311-329. · Zbl 0659.65098 |

[11] | J. H. Bramble, J. E. Pasciak, J. P. Wang, and J. C. Xu, Convergence estimates for multigrid algorithms without regularity assumptions, Math. Comp., 57 (1991), pp. 23-45. · Zbl 0727.65101 |

[12] | W. L. Briggs, V. E. Henson, and S. F. Mccormick, A Multigrid Tutorial, SIAM, Philadelphia, 2000. · Zbl 0958.65128 |

[13] | R. H. Chan, Q. S. Chang, and H. W. Sun, Multigrid method for ill-conditioned symmetric Toeplitz systems, SIAM J. Sci. Comput., 19 (1998), pp. 516-529. · Zbl 0916.65029 |

[14] | R. H. Chan and X. Q. Jin, An Introduction to Iterative Toeplitz Solvers, SIAM, Philadelphia, 2007. · Zbl 1146.65028 |

[15] | L. Chen, R. H. Nochetto, E. Otárola, and A. J. Salgado, Multilevel methods for nonuniformly elliptic operators and fractional diffusion, Math. Comp., 85 (2016), pp. 2583-2607. · Zbl 1344.65117 |

[16] | M. H. Chen, W. Y. Qi, and Y. T. Wang, Uniform convergence of V-cycle multigrid finite element method for one-dimensional time-dependent fractional problem, Appl. Math. Lett., 98 (2019), pp. 49-56. · Zbl 1464.65111 |

[17] | M. H. Chen and W. H. Deng, High order algorithms for the fractional substantial diffusion equation with truncated Levy flights, SIAM J. Sci. Comput., 37 (2015), pp. A890-A917. · Zbl 1317.65198 |

[18] | M. H. Chen and W. H. Deng, Convergence analysis of a multigrid method for a nonlocal model, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 869-890. · Zbl 1373.65068 |

[19] | M. H. Chen, W. H. Deng, and S. Serra-Capizzano, Uniform convergence of V-cycle multigrid algorithms for two-dimensional fractional Feynman-Kac equation, J. Sci. Comput., 74 (2018), pp. 1034-1059. · Zbl 1397.65177 |

[20] | M. H. Chen, Y. T. Wang, X. Cheng, and W. H. Deng, Second-order LOD multigrid method for multidimensional Riesz fractional diffusion equation, BIT, 54 (2014), pp. 623-647. · Zbl 1301.35200 |

[21] | M. D’Elia and M. Gunzburger, The fractional Laplacian operator on bounded domains as a special case of the nonlocal diffusion operator, Comput. Math. Appl., 66 (2013), pp. 1254-1260. · Zbl 1345.35128 |

[22] | M. Donatelli, M. Mazza, and S. Serra-Capizzano, Spectral analysis and structure preserving preconditioners for fractional diffusion equations, J. Comput. Phys., 307 (2016), pp. 262-279. · Zbl 1352.65305 |

[23] | Q. Du, M. Gunzburger, R. Lehoucq, and K. Zhou, Analysis and approximation of nonlocal diffusion problems with volume constraints, SIAM Rev., 56 (2012), pp. 676-696. · Zbl 1422.76168 |

[24] | G. Fiorentino and S. Serra-Capizzano, Multigrid methods for symmetric positive definite block Toeplitz matrices with nonnegative generating functions, SIAM J. Sci. Comput., 17 (1996), pp. 1068-1081. · Zbl 0858.65039 |

[25] | W. Hackbusch, Multigrid Methods and Applications, Springer-Verlag, Berlin, 1985. · Zbl 0595.65106 |

[26] | R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, New York, 2013. · Zbl 1267.15001 |

[27] | Y. H. Huang and A. Oberman, Numerical methods for the fractional Laplacian: A finite difference-quadrature approach, SIAM J. Numer. Anal., 52 (2014), pp. 3056-3084. · Zbl 1316.65071 |

[28] | Y. J. Jiang and X. J. Xu, Multigrid methods for space fractional partial differential equations, J. Comput. Phys., 302 (2015), pp. 374-392. · Zbl 1349.65620 |

[29] | M. Kwaśnicki, Ten equivalent definitions of the fractional Laplace operator, Fract. Calc. Appl. Anal., 20 (2017), pp. 7-51. · Zbl 1375.47038 |

[30] | T. Mengesha and Q. Du, Analysis of a scalar nonlocal peridynamic model with a sign changing kernel, Discrete Contin. Dyn. Syst. B, 18 (2013), pp. 1415-1437. · Zbl 1278.45014 |

[31] | H. Moghaderi, M. Dehghan, M. Donatelli, and M. Mazza, Spectral analysis and multigrid preconditioners for two-dimensional space-fractional diffusion equations, J. Comput. Phys., 350 (2017), pp. 992-1011. · Zbl 1380.65240 |

[32] | M. Ng, S. Serra-Capizzano, and C. Tablino-Possio, Multigrid method for symmetric sinc-Galerkin systems, Numer. Linear Algebra Appl., 12 (2005), pp. 261-269. · Zbl 1164.65522 |

[33] | H. Pang and H. Sun, Multigrid method for fractional diffusion equations, J. Comput. Phys., 231 (2012), pp. 693-703. · Zbl 1243.65117 |

[34] | J. Pang, R. Ke, M. Ng, and H. Sun, Preconditioning techniques for diagonal-times-Toeplitz matrices in fractional diffusion equations, SIAM J. Sci. Comput., 36 (2014), pp. A2698-A2719. · Zbl 1314.65112 |

[35] | J. Ruge and K. Stüben, Algebraic Multigrid, in Multigrid Methods, S. McCormick, ed., SIAM, Philadelphia, 1987, pp. 73-130. |

[36] | Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, 2003. · Zbl 1031.65046 |

[37] | S. Serra-Capizzano, On the extreme spectral properties of Toeplitz matrices generated by \(L1\) functions with several minima/maxima, BIT, 36 (1996), pp. 135-142. · Zbl 0851.15008 |

[38] | S. Serra-Capizzano, On the extreme eigenvalues of Hermitian (block) Toeplitz matrices, Linear Algebra Appl., 270 (1998), pp. 109-129. · Zbl 0892.15014 |

[39] | S. Serra-Capizzano, Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs matrix-sequences, Numer. Math., 92 (2002), pp. 433-465. · Zbl 1013.65026 |

[40] | S. Serra-Capizzano and C. Tablino-Possio, Two-grid methods for Hermitian positive definite linear systems connected with an order relation, Calcolo, 51 (2014), pp. 261-285. · Zbl 1311.65034 |

[41] | S. A. Silling, Reformulation of elasticity theory for discontinuities and long-range forces, J. Mech. Phys. Solids, 48 (2000), pp. 175-209. · Zbl 0970.74030 |

[42] | K. Stüben, A review of algebraic multigrid, J. Comput. Appl. Math., 128 (2001), pp. 281-309. · Zbl 0979.65111 |

[43] | X. C. Tian and Q. Du, Analysis and comparison of different approximations to nonlocal diffusion and linear peridynamic equations, SIAM J. Numer. Anal., 51 (2013), pp. 3458-3482. · Zbl 1295.82021 |

[44] | W. Wang and H. Tian, A fast Galerkin method with efficient matrix assembly and storage for a peridynamic model, J. Comput. Phys., 231 (2012), pp. 7730-7738. · Zbl 1254.74112 |

[45] | J. Xu, An introduction to multilevel methods, in Wavelets, Multilevel Methods and Elliptic PDEs, M. Ainsworth, J. Levesley, W. A. Light, and M. Marletta, eds., Oxford University Press, New York, 1997, pp. 213-302. · Zbl 0903.65095 |

[46] | J. Xu and L. Zikatanov, Algebraic multigrid methods, Acta Numer., 26 (2017), pp. 591-721. · Zbl 1378.65182 |

[47] | Z. J. Zhang, W. H. Deng, and G. E. Karniadakis, A Riesz basis Galerkin method for the tempered fractional Laplacian, SIAM J. Numer. Anal., 56 (2018), pp. 3010-3039. · Zbl 1402.65120 |

[48] | A. Zoia, A. Rosso, and M. Kardar, Fractional Laplacian in bounded domains, Phys. Rev. E, 76 (2007), 021116. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.