Communications on Applied Mathematics and Computation >

2022 , Vol. 4 >Issue 4: 1416 - 1440

DOI: https://doi.org/10.1007/s42967-021-00184-9

Space-Fractional Diffusion with Variable Order and Diffusivity:Discretization and Direct Solution Strategies

Expand
  • King Abdullah University of Science and Technology, Thuwal, Saudi Arabia

Received date: 2021-08-16

  Revised date: 2021-11-22

  Online published: 2022-09-26

Supported by

The authors acknowledge the support of the Extreme Computing Research Center at KAUST.

Fold

Abstract

We consider the multidimensional space-fractional diffusion equations with spatially varying diffusivity and fractional order. Significant computational challenges are encountered when solving these equations due to the kernel singularity in the fractional integral operator and the resulting dense discretized operators, which quickly become prohibitively expensive to handle because of their memory and arithmetic complexities. In this work, we present a singularity-aware discretization scheme that regularizes the singular integrals through a singularity subtraction technique adapted to the spatial variability of diffusivity and fractional order. This regularization strategy is conveniently formulated as a sparse matrix correction that is added to the dense operator, and is applicable to different formulations of fractional diffusion equations. We also present a block low rank representation to handle the dense matrix representations, by exploiting the ability to approximate blocks of the resulting formally dense matrix by low rank factorizations. A Cholesky factorization solver operates directly on this representation using the low rank blocks as its atomic computational tiles, and achieves high performance on multicore hardware. Numerical results show that the singularity treatment is robust, substantially reduces discretization errors, and attains the first-order convergence rate allowed by the regularity of the solutions. They also show that considerable savings are obtained in storage (O(N1.5)) and computational cost (O(N2)) compared to dense factorizations. This translates to orders-of-magnitude savings in memory and time on multidimensional problems, and shows that the proposed methods offer practical tools for tackling large nonlocal fractional diffusion simulations.

Key words： Fractional diffusion; Variable order; Variable diffusivity; Singularity subtraction; Block low rank matrix; Tile low rank (TLR) Cholesky

Cite this article

Hasnaa Alzahrani, George Turkiyyah, Omar Knio, David Keyes . Space-Fractional Diffusion with Variable Order and Diffusivity:Discretization and Direct Solution Strategies[J]. Communications on Applied Mathematics and Computation, 2022 , 4(4) : 1416 -1440 . DOI: 10.1007/s42967-021-00184-9

References

1. Acosta, G., Bersetche, F.M., Borthagaray, J.P.:A short FE implementation for a 2D homogeneous Dirichlet problem of a fractional Laplacian. Computers & Mathematics with Applications 74(4), 784-816 (2017). https://www.sciencedirect.com/science/article/pii/S0898122117303310
2. Bebendorf, M.:Why finite element discretizations can be factored by triangular hierarchical matrices. SIAM J. Numer. Anal. 45(4), 1472-1494 (2007)
3. Bebendorf, M., Hackbusch, W.:Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L∞-coefficients. Numer. Math. 95(1), 1-28 (2003)
4. Bolin, D., Kirchner, K., Kovács, M.:Numerical solution of fractional elliptic stochastic PDEs with spatial white noise. IMA J. Numer. Anal. 40(2), 1051-1073 (2018). https://doi.org/10.1093/imanum/dry091
5. Börm, S.:Efficient numerical methods for non-local operators:H2-matrix compression, algorithms and analysis, vol. 14. European Mathematical Society (2010)
6. Boukaram, W., Lucchesi, M., Turkiyyah, G., Le Maître, O., Knio, O., Keyes, D.:Hierarchical matrix approximations for space-fractional diffusion equations. Computer Methods in Applied Mechanics and Engineering 369, 113191 (2020). https://www.sciencedirect.com/science/article/pii/S0045782520303765
7. Boukaram, W., Turkiyyah, G., Keyes, D.:Hierarchical matrix operations on GPUs:matrix-vector multiplication and compression. ACM Trans. Math. Softw. 45(1), 3:1-3:28 (2019). https://doi.org/10.1145/3232850
8. Boukaram, W., Turkiyyah, G., Keyes, D.:Randomized GPU algorithms for the construction of hierarchical matrices from matrix-vector operations. SIAM J. Sci. Comput. 41(4), C339-C366 (2019). https://doi.org/10.1137/18M1210101
9. Boukaram, W., Zampini, S., Turkiyyah, G., Keyes, D.:H2OPUS-TLR:high performance tile low rank symmetric factorizations using adaptive randomized approximation (2021). http://arxiv.org/abs/2108.11932
10. D'Elia, M., De Los Reyes, J.C., Miniguano-Trujillo, A.:Bilevel parameter learning for nonlocal image denoising models. J. Math. Imaging Vis. 63(6), 753-775 (2021). https://doi.org/10.1007/s10851-021-01026-2
11. D'Elia, M., Du, Q., Glusa, C., Gunzburger, M., Tian, X., Zhou, Z.:Numerical methods for nonlocal and fractional models. Acta Numer. 29, 1-124 (2020). https://doi.org/10.1017/S096249292000001X
12. D'Elia, M., Tian, X., Yu, Y.:A physically consistent, flexible, and efficient strategy to convert local boundary conditions into nonlocal volume constraints. SIAM J. Sci. Comput. 42(4), A1935-A1949 (2020). https://doi.org/10.1137/19M1266617
13. Du, N., Wang, H.:A fast finite element method for space-fractional dispersion equations on bounded domains in R2. SIAM J. Sci. Comput. 37(3), A1614-A1635 (2015). https://doi.org/10.1137/15M1007458
14. Du, Q.:Nonlocal Modeling, Analysis, and Computation. SIAM (2019)
15. Du, Q., Gunzburger, M., Lehoucq, R., Zhou, K.:A nonlocal vector calculus, nonlocal volume-constrained problems, and nonlocal balance laws. Math. Models Methods Appl. Sci. 23, 493-540 (2013)
16. 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
17. Duo, S., van Wyk, H.W., Zhang, Y.:A novel and accurate finite difference method for the fractional Laplacian and the fractional Poisson problem. J. Comput. Phys. 355, 233-252 (2018). https://www.sciencedirect.com/science/article/pii/S0021999117308495
18. Duo, S., Zhang, Y.:Accurate numerical methods for two and three dimensional integral fractional Laplacian with applications. Comput. Methods Appl. Mech. Eng. 355, 639-662 (2019). https://www.sciencedirect.com/science/article/pii/S0045782519303597
19. 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
20. Gillman, A., Young, P.M., Martinsson, P.G.:A direct solver with O(N) complexity for integral equations on one-dimensional domains. Front. Math. China 7(2), 217-247 (2012). https://doi.org/10.1007/s11464-012-0188-3
21. Hackbusch, W.:Hierarchical Matrices:Algorithms and Analysis. Springer-Verlag, Berlin, Heidelberg (2015)
22. Hackbusch, W., Börm, S.:H2-matrix approximation of integral operators by interpolation. Applied Numerical Mathematics 43(1), 129-143 (2002). https://www.sciencedirect.com/science/article/pii/S0168927402001216
23. Halko, N., Martinsson, P.G., Tropp, J.A.:Finding structure with randomness:probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217-288 (2011). https://doi.org/10.1137/090771806
24. Jia, J., Zheng, X., Fu, H., Dai, P., Wang, H.:A fast method for variable-order space-fractional diffusion equations. Numer. Algorithms 85(4), 1519-1540 (2020). https://doi.org/10.1007/s11075-020-00875-z
25. Karkulik, M., Melenk, J.M.:H-matrix approximability of inverses of discretizations of the fractional Laplacian. Adv. Comput. Math. 46 (2019)
26. Keyes, D.E., Ltaief, H., Turkiyyah, G.:Hierarchical algorithms on hierarchical architectures. Philos. Trans. R. Soc. A Math. Phys. Eng. Sci. 378(2166), 20190055 (2020). https://royalsocietypublishing.org/doi/abs/10.1098/rsta.2019.0055
27. Kwaśnicki, M.:Ten equivalent definitions of the fractional Laplace operator. Fract. Calc. Appl. Anal. 20(1), 7-51 (2017)
28. Lischke, A., Pang, G., Gulian, M., Song, F., Glusa, C., Zheng, X., Mao, Z., Cai, W., Meerschaert, M.M., Ainsworth, M., Karniadakis, G.E.:What is the fractional Laplacian? A comparative review with new results. J. Comput. Phys. 404, 109009 (2020). https://www.sciencedirect.com/science/article/pii/S0021999119307156
29. Lucchesi, M., Allouch, S., Le Maître, O.P., Mustapha, K.A., Knio, O.M.:Particle simulation of space-fractional diffusion equations. Comput. Part. Mech. 7(3), 491-507 (2020). https://doi.org/10.1007/s40571-019-00275-8
30. Massei, S., Mazza, M., Robol, L.:Fast solvers for two-dimensional fractional diffusion equations using rank structured matrices. SIAM J. Sci. Comput. 41(4), A2627-A2656 (2019). https://doi.org/10.1137/18M1180803
31. Minden, V., Ying, L.:A simple solver for the fractional Laplacian in multiple dimensions. SIAM J. Sci. Comput. 42(2), A878-A900 (2020). https://doi.org/10.1137/18M1170406
32. Mustapha, K.A., Furati, K.M., Knio, O.M., Le Maître, O.P.:A finite difference method for space fractional differential equations with variable diffusivity coefficient. Commun. Appl. Math. Comput. 2(4), 671-688 (2020). https://doi.org/10.1007/s42967-020-00066-6
33. Pang, G., Lu, L., Karniadakis, G.E.:fPINNs:fractional physics-informed neural networks. SIAM J. Sci. Comput. 41(2), A2603-A2626 (2019). https://doi.org/10.1137/18M1229845
34. Pozrikidis, C.:The Fractional Laplacian. CRC Press (2016)
35. Samko, S.:Fractional integration and differentiation of variable order:an overview. Nonlinear Dyn. 71, 653-662 (2013). https://doi.org/10.1007/s11071-012-0485-0
36. Xia, J., Chandrasekaran, S., Gu, M., Li, X.S.:Fast algorithms for hierarchically semiseparable matrices. Numer. Linear Algebra Appl. 17(6), 953-976 (2010). https://onlinelibrary.wiley.com/doi/abs/10.1002/nla.691
37. Xu, K., Darve, E.:Efficient numerical method for models driven by Lévy process via hierarchical matrices (2018). http://arxiv.org/abs/1812.08324
38. Xu, K., Darve, E.:Isogeometric collocation method for the fractional Laplacian in the 2D bounded domain. Comput. Methods Appl. Mech. Eng. 364, 112936 (2020). https://www.sciencedirect.com/science/article/pii/S0045782520301195
39. Zampini, S., Boukaram, W., Turkiyyah, G., Knio, O., Keyes, D.E.:H2Opus:a distributed-memory multi-GPU software package for non-local operators (2021). http://arxiv.org/abs/2109.05451
40. Zhao, X., Hu, X., Cai, W., Karniadakis, G.E.:Adaptive finite element method for fractional differential equations using hierarchical matrices. Comput. Methods Appl. Mech. Eng. 325, 56-76 (2017)
Options
Outlines

/

〈 〉

Copyright © Editorial By Communications on Applied Mathematics and Computation
沪ICP备09014157