Top

Computing and Visualization in Science

Published in:

08-02-2019 | Original Article

Exploiting multilevel Toeplitz structures in high dimensional nonlocal diffusion

Authors: Christian Vollmann, Volker Schulz

Published in: Computing and Visualization in Science | Issue 1-2/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We present a finite element implementation for the steady-state nonlocal Dirichlet problem with homogeneous volume constraints. Here, the nonlocal diffusion operator is defined as integral operator characterized by a certain kernel function. We assume that the domain is an arbitrary d-dimensional hyperrectangle and the kernel is translation and reflection invariant. Under these assumptions, we carefully analyze the structure of the stiffness matrix resulting from a continuous Galerkin method with \(Q_1\) elements and exploit this structure in order to cope with the curse of dimensionality associated to nonlocal problems. For the purpose of illustration we choose a particular kernel, which is related to space-fractional diffusion and present numerical results in 1d, 2d and for the first time also in 3d.

previous article Numerical solution of a phase field model for polycrystallization processes in binary mixtures

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Acosta, G., Bersetche, F.M., Borthagaray, J.P.: A short FE implementation for a 2d homogeneous Dirichlet problem of a fractional Laplacian. Comput. Math. Appl. (2017). https://doi.org/10.1016/j.camwa.2017.05.026. http://www.sciencedirect.com/science/article/pii/S0898122117303310

Acosta, G., Borthagaray, J.P.: A fractional Laplace equation: regularity of solutions and finite element approximations. SIAM J. Numer. Anal. 55(2), 472–495 (2017). https://doi.org/10.1137/15M1033952 MathSciNetCrossRefMATH

Bass, R.F., Kassmann, M., Kumagai, T.: Symmetric jump processes: localization, heat kernels and convergence. Ann. Inst. H. Poincaré Probab. Stat. 46(1), 59–71 (2010). https://doi.org/10.1214/08-AIHP201 MathSciNetCrossRefMATH

Burkovska, O., Gunzburger, M.: Regularity and approximation analyses of nonlocal variational equality and inequality problems. arXiv preprint. arXiv:1804.10282 (2018)

Capizzano, S.S., Tyrtyshnikov, E.E.: Any circulant-like preconditioner for multilevel matrices is not superlinear. SIAM J. Matrix Anal. Appl. 21, 431–439 (2000)MathSciNetCrossRefMATH

Chan, T.F.: An optimal circulant preconditioner for Toeplitz systems. SIAM J. Sci. Stat. Comput. 9(4), 766–771 (1988)MathSciNetCrossRefMATH

Chen, J., Li, T.L., Anitescu, M.: A parallel linear solver for multilevel Toeplitz systems with possibly several right-hand sides. Parallel Comput. 40(8), 408–424 (2014). https://doi.org/10.1016/j.parco.2014.06.004. http://www.sciencedirect.com/science/article/pii/S0167819114000672

Chen, M., Deng, W.: Convergence proof for the multigrid method of the nonlocal model. arXiv preprint. arXiv:1605.05481 (2016)

Du, Q., Gunzburger, M., Lehoucq, R.B., Zhou, K.: Analysis and approximation of nonlocal diffusion problems with volume constraints. SIAM Rev. 54(4), 667–696 (2012). https://doi.org/10.1137/110833294 MathSciNetCrossRefMATH

10.

Du, Q., Gunzburger, M., Lehoucq, R.B., Zhou, K.: A nonlocal vector calculus, nonlocal volume-constrained problems, and nonlocal balance laws. Math. Models Methods Appl. Sci. 23(03), 493–540 (2013). https://doi.org/10.1142/S0218202512500546 MathSciNetCrossRefMATH

11.

Du, Q., Zhou, K.: Mathematical analysis for the peridynamic nonlocal continuum theory. ESAIM: M2AN 45(2), 217–234 (2011). https://doi.org/10.1051/m2an/2010040

12.

D’Elia, M., Gunzburger, M.: The fractional Laplacian operator on bounded domains as a special case of the nonlocal diffusion operator. Comput. Math. Appl. 66(7), 1245–1260 (2013). https://doi.org/10.1016/j.camwa.2013.07.022. http://www.sciencedirect.com/science/article/pii/S0898122113004707

13.

Gilboa, G., Osher, S.: Nonlocal operators with applications to image processing. Multiscale Model. Simul. 7(3), 1005–1028 (2009). https://doi.org/10.1137/070698592 MathSciNetCrossRefMATH

14.

Elman, Howard, Silvester, David, Wathen, Andy: Finite Elements and Fast Iterative Solvers. Oxford University Press, New York (2005)MATH

15.

Barlow, Martin T., Bass, Richard F., Chen, Zhen-Qing, Krassmann, Moritz: Non-local Dirichlet forms and symmetric jump processes. Trans. Am. Math. Soc. 361(4), 1963–1999 (2009). https://doi.org/10.1090/S0002-9947-08-04544-3 MathSciNetCrossRefMATH

16.

Nocedale, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999). https://doi.org/10.1007/978-0-387-40065-5 CrossRef

17.

Olshanskii, M.A., Tyrtyshnikov, E.E.: Iterative methods for linear systems: theory and applications. SIAM (2014)

18.

Olshevsky, V., Oseledets, I., Tyrtyshnikov, E.: Tensor properties of multilevel Toeplitz and related matrices. Linear Algebra Appl. 412(1), 1–21 (2006). https://doi.org/10.1016/j.laa.2005.03.040. http://www.sciencedirect.com/science/article/pii/S002437950500296X

19.

Pang, H.K., Sun, H.W.: Multigrid method for fractional diffusion equations. J. Comput. Phys. 231(2), 693–703 (2012). https://doi.org/10.1016/j.jcp.2011.10.005. http://www.sciencedirect.com/science/article/pii/S0021999111005985

20.

Peyré, G., Bougleux, S., Cohen, L.: Non-local regularization of inverse problems, pp. 57–68. Springer Berlin Heidelberg, Berlin, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88690-7_5

21.

Rosasco, L., Belkin, M., Vito, E.D.: On learning with integral operators. J. Mach. Learn. Res. 11, 905–934 (2010). http://dl.acm.org/citation.cfm?id=1756006.1756036

22.

Serra-Capizzano, S.: Toeplitz matrices: spectral properties and preconditioning in the cg method (2007)

23.

Wang, H., Basu, T.S.: A fast finite difference method for two-dimensional space-fractional diffusion equations. SIAM J. Sci. Comput. 34(5), A2444–A2458 (2012). https://doi.org/10.1137/12086491X MathSciNetCrossRefMATH

24.

Wang, H., Du, N.: A fast finite difference method for three-dimensional time-dependent space-fractional diffusion equations and its efficient implementation. J. Comput. Phys. 253, 50–63 (2013). https://doi.org/10.1016/j.jcp.2013.06.040. http://www.sciencedirect.com/science/article/pii/S0021999113004701

25.

Wang, H., Wang, K., Sircar, T.: A direct o(nlog2n) finite difference method for fractional diffusion equations. J. Comput. Phys. 229(21), 8095–8104 (2010). https://doi.org/10.1016/j.jcp.2010.07.011. http://www.sciencedirect.com/science/article/pii/S0021999110003943

26.

Ye, K., Lim, L.H.: Algorithms for structured matrix-vector product of optimal bilinear complexity. In: 2016 IEEE Information Theory Workshop (ITW), pp. 310–314 (2016). https://doi.org/10.1109/ITW.2016.7606846

27.

Zhou, K., Du, Q.: Mathematical and numerical analysis of linear peridynamic models with nonlocal boundary conditions. SIAM J. Numer. Anal. 48(5), 1759–1780 (2010). https://doi.org/10.1137/090781267 MathSciNetCrossRefMATH

Title: Exploiting multilevel Toeplitz structures in high dimensional nonlocal diffusion
Authors: Christian Vollmann
Volker Schulz
Publication date: 08-02-2019
Publisher: Springer Berlin Heidelberg
Published in: Computing and Visualization in Science / Issue 1-2/2019
Print ISSN: 1432-9360
Electronic ISSN: 1433-0369
DOI: https://doi.org/10.1007/s00791-018-00306-6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner