2019
Journal article
Open Access
Fast solvers for two-dimensional fractional diffusion equations using rank structured matrices
Massei S., Mazza M., Robol L.
Computational Mathematics Fractional operators FOS: Mathematics Sylvester equation Hierarchical matrices Fractional diffusion Structured matrices Mathematics - Numerical Analysis 15A24 65F10 35R11 Applied Mathematics Numerical Analysis (math.NA)
We consider the discretization of time-space diffusion equations with fractional derivatives in space and either one-dimensional (1D) or 2D spatial domains. The use of an implicit Euler scheme in time and finite differences or finite elements in space leads to a sequence of dense large scale linear systems describing the behavior of the solution over a time interval. We prove that the coefficient matrices arising in the 1D context are rank structured and can be efficiently represented using hierarchical formats (\scrH -matrices, HODLR). Quantitative estimates for the rank of the off-diagonal blocks of these matrices are presented. We analyze the use of HODLR arithmetic for solving the 1D case and we compare this strategy with existing methods that exploit the Toeplitz-like structure to precondition the GMRES iteration. The numerical tests demonstrate the convenience of the HODLR format when at least a reasonably low number of time steps is needed. Finally, we explain how these properties can be leveraged to design fast solvers for problems with 2D spatial domains that can be reformulated as matrix equations. The experiments show that the approach based on the use of rank-structured arithmetic is particularly effective and outperforms current state of the art techniques.
Source: SIAM journal on scientific computing (Print) 41 (2019): A2627–A2656. doi:10.1137/18M1180803
Publisher: Society for Industrial and Applied Mathematics,, Philadelphia, PA , Stati Uniti d'America
[1] ITER - the way to new energy. https://www.iter.org/.
[2] J. Bai and X.-C. Feng. Fractional-order anisotropic di usion for image denoising. IEEE Trans. Image Process., 16(10):2492{2502, 2007.
[3] B. Beckermann. An error analysis for rational Galerkin projection applied to the Sylvester equation. SIAM J. Numer. Anal., 49(6):2430{2450, 2011.
[4] B. Beckermann and A. Townsend. On the singular values of matrices with displacement structure. SIAM J. Matrix Anal. Appl., 38(4):1227{1248, 2017.
[5] M. Berljafa and S. Guttel. Generalized rational Krylov decompositions with an application to rational approximation. SIAM J. Matrix Anal. Appl., 36(2):894{916, 2015.
[6] R. Bhatia. In nitely divisible matrices. Amer. Math. Monthly, 113(3):221{235, 2006.
[7] S. Borm, L. Grasedyck, and W. Hackbusch. Hierarchical matrices. Lect. notes, 21:2003, 2003.
[8] T. Breiten, V. Simoncini, and M. Stoll. Low-rank solvers for fractional di erential equations. Electron. Trans. Numer. Anal., 45:107{132, 2016.
[9] L. A. Ca arelli and P. R. Stinga. Fractional elliptic equations, caccioppoli estimates and regularity. arXiv:1409.7721v3, 2017.
[10] D. del Castillo-Negrete, B. Carreras, and V. Lynch. Fractional di usion in plasma turbulence. Phys. Plasmas, 11(8):3854{3864, 2004.
[11] W. Deng, B. Li, W. Tian, and P. Zhang. Boundary problems for the fractional and tempered fractional operators. Multiscale Model. Simul., 16(1):125{149, 2018.
[12] M. Donatelli, M. Mazza, and S. Serra-Capizzano. Spectral analysis and structure preserving preconditioners for fractional di usion equations. J. Comput. Phys., 307:262{279, 2016.
[13] B. Duan, Z. Zheng, and W. Cao. Finite element method for a kind of two-dimensional space-fractional diffusion equation with its implementation. American Journal of Computational Mathematics, 5(02):135, 2015.
[14] Y. Eidelman, I. Gohberg, and I. Haimovici. Separable type representations of matrices and fast algorithms. Vol. 1, volume 234 of Operator Theory: Advances and Applications. Birkhauser/Springer, Basel, 2014.
[15] V. J. Ervin and J. P. Roop. Variational formulation for the stationary fractional advection dispersion equation. Numer. Methods Partial Di erential Equations, 22(3):558{576, 2006.
[16] D. Fasino. Spectral properties of Toeplitz-plus-Hankel matrices. Calcolo, 33(1-2):87{98 (1998), 1996. Toeplitz matrices: structures, algorithms and applications (Cortona, 1996).
[17] M. Fiedler. Notes on Hilbert and Cauchy matrices. Linear Algebra Appl., 432(1):351{356, 2010.
[18] C. Garoni and S. Serra-Capizzano. Generalized locally Toeplitz sequences: theory and applications. Vol. I. Springer, Cham, 2017.
[19] G. H. Golub, F. T. Luk, and M. L. Overton. A block Lanczos method for computing the singular values of corresponding singular vectors of a matrix. ACM Trans. Math. Software, 7(2):149{169, 1981.
[20] L. Grasedyck. Singular value bounds for the cauchy matrix and solutions to sylvester equations. Technical report, Technical report 13, Germany: University Kiel, 2001.
[21] L. Grasedyck, W. Hackbusch, and S. Le Borne. Adaptive geometrically balanced clustering of H -matrices. Computing, 73(1):1{23, 2004.
[22] M. H. Gutknecht. Block krylov space methods for linear systems with multiple right-hand sides. In The Joint Workshop on Computational Chemistry and Numerical Analysis (CCNA2005), 2005.
[23] W. Hackbusch. A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices. Computing, 62(2):89{108, 1999.
[24] W. Hackbusch. Hierarchical matrices: algorithms and analysis, volume 49. Springer, 2015.
[25] M. Heyouni. Extended Arnoldi methods for large low-rank Sylvester matrix equations. Appl. Numer. Math., 60(11):1171{1182, 2010.
[26] X.-Q. Jin, F.-R. Lin, and Z. Zhao. Preconditioned iterative methods for two-dimensional space-fractional di usion equations. Commun. Comput. Phys., 18(2):469{488, 2015.
[27] L. Knizhnerman and V. Simoncini. Convergence analysis of the extended Krylov subspace method for the Lyapunov equation. Numer. Math., 118(3):567{586, 2011.
[28] D. Kressner, S. Massei, and L. Robol. Low-rank updates and a divide-and-conquer method for linear matrix equations. arXiv preprint arXiv:1712.04349, 2017.
[29] S.-L. Lei and H.-W. Sun. A circulant preconditioner for fractional di usion equations. J. Comput. Phys., 242:715{725, 2013.
[30] Z. Lin and D. Wang. A nite element formulation preserving symmetric and banded di usion sti ness matrix characteristics for fractional di erential equations. Comput. Mech., pages 1{27, 2017.
[31] Y. Liu, Y. Yan, and M. Khan. Discontinuous Galerkin time stepping method for solving linear space fractional partial di erential equations. Appl. Numer. Math., 115:200{213, 2017.
[32] S. Massei, D. Palitta, and L. Robol. Solving rank structured Sylvester and Lyapunov equations. arXiv preprint arXiv:1711.05493, 2017.
[33] S. Massei and L. Robol. Hierarchical matrix toolbox. GitHub repository: https://github.com/numpi/hmtoolbox/, 2015.
[34] M. M. Meerschaert and C. Tadjeran. Finite di erence approximations for fractional advection-dispersion ow equations. J. Comput. Appl. Math., 172(1):65{77, 2004.
[35] H. Moghaderi, M. Dehghan, M. Donatelli, and M. Mazza. Spectral analysis and multigrid preconditioners for two-dimensional space-fractional di usion equations. J. Comput. Phys., 350:992{1011, 2017.
[36] J. Pan, M. Ng, and H. Wang. Fast preconditioned iterative methods for nite volume discretization of steady-state space-fractional di usion equations. Numer. Algorithms, 74(1):153{173, 2017.
[37] J. Pan, M. K. Ng, and H. Wang. Fast iterative solvers for linear systems arising from time-dependent space-fractional di usion equations. SIAM J. Sci. Comput., 38(5):A2806{A2826, 2016.
[38] H.-K. Pang and H.-W. Sun. Multigrid method for fractional di usion equations. J. Comput. Phys., 231(2):693{703, 2012.
[39] I. Podlubny. Fractional di erential equations: an introduction to fractional derivatives, fractional di erential equations, to methods of their solution and some of their applications, volume 198. Academic press, 1998.
[40] M. Raberto, E. Scalas, and F. Mainardi. Waiting-times and returns in high-frequency nancial data: an empirical study. Physica A, 314(1):749{755, 2002.
[41] J. P. Roop. Computational aspects of FEM approximation of fractional advection dispersion equations on bounded domains in R2. J. Comput. Appl. Math., 193(1):243{268, 2006.
[42] H. D. Simon and H. Zha. Low-rank matrix approximation using the Lanczos bidiagonalization process with applications. SIAM J. Sci. Comput., 21(6):2257{2274, 2000.
[43] V. Simoncini. A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput., 29(3):1268{1288, 2007.
[44] W. Tian, H. Zhou, and W. Deng. A class of second order di erence approximations for solving space fractional di usion equations. Math. Comp., 84(294):1703{1727, 2015.
[45] A. Townsend. Computing with functions in two dimensions. PhD thesis, University of Oxford, 2014.
[46] A. Townsend and L. N. Trefethen. An extension of Chebfun to two dimensions. SIAM J. Sci. Comput., 35(6):C495{C518, 2013.
[47] R. Vandebril, M. Van Barel, and N. Mastronardi. Matrix computations and semiseparable matrices. Linear systems, volume 1. Johns Hopkins University Press, Baltimore, MD, 2008.
[48] H. Wang, K. Wang, and T. Sircar. A direct O(N log2 N ) nite di erence method for fractional di usion equations. J. Comput. Phys., 229(21):8095{8104, 2010.
[49] R. Wang, Y. Li, M. W. Mahoney, and E. Darve. Structured block basis factorization for scalable kernel matrix evaluation. arXiv preprint arXiv:1505.00398, 2015.
[50] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li. Fast algorithms for hierarchically semiseparable matrices. Numer. Linear Algebra Appl., 17(6):953{976, 2010.
[51] X. Zhao, X. Hu, W. Cai, and G. E. Karniadakis. Adaptive nite element method for fractional di erential equations using hierarchical matrices. Comput. Methods Appl. Mech. Engrg., 325:56{76, 2017.
[2] J. Bai and X.-C. Feng. Fractional-order anisotropic di usion for image denoising. IEEE Trans. Image Process., 16(10):2492{2502, 2007.
[3] B. Beckermann. An error analysis for rational Galerkin projection applied to the Sylvester equation. SIAM J. Numer. Anal., 49(6):2430{2450, 2011.
[4] B. Beckermann and A. Townsend. On the singular values of matrices with displacement structure. SIAM J. Matrix Anal. Appl., 38(4):1227{1248, 2017.
[5] M. Berljafa and S. Guttel. Generalized rational Krylov decompositions with an application to rational approximation. SIAM J. Matrix Anal. Appl., 36(2):894{916, 2015.
[6] R. Bhatia. In nitely divisible matrices. Amer. Math. Monthly, 113(3):221{235, 2006.
[7] S. Borm, L. Grasedyck, and W. Hackbusch. Hierarchical matrices. Lect. notes, 21:2003, 2003.
[8] T. Breiten, V. Simoncini, and M. Stoll. Low-rank solvers for fractional di erential equations. Electron. Trans. Numer. Anal., 45:107{132, 2016.
[9] L. A. Ca arelli and P. R. Stinga. Fractional elliptic equations, caccioppoli estimates and regularity. arXiv:1409.7721v3, 2017.
[10] D. del Castillo-Negrete, B. Carreras, and V. Lynch. Fractional di usion in plasma turbulence. Phys. Plasmas, 11(8):3854{3864, 2004.
[11] W. Deng, B. Li, W. Tian, and P. Zhang. Boundary problems for the fractional and tempered fractional operators. Multiscale Model. Simul., 16(1):125{149, 2018.
[12] M. Donatelli, M. Mazza, and S. Serra-Capizzano. Spectral analysis and structure preserving preconditioners for fractional di usion equations. J. Comput. Phys., 307:262{279, 2016.
[13] B. Duan, Z. Zheng, and W. Cao. Finite element method for a kind of two-dimensional space-fractional diffusion equation with its implementation. American Journal of Computational Mathematics, 5(02):135, 2015.
[14] Y. Eidelman, I. Gohberg, and I. Haimovici. Separable type representations of matrices and fast algorithms. Vol. 1, volume 234 of Operator Theory: Advances and Applications. Birkhauser/Springer, Basel, 2014.
[15] V. J. Ervin and J. P. Roop. Variational formulation for the stationary fractional advection dispersion equation. Numer. Methods Partial Di erential Equations, 22(3):558{576, 2006.
[16] D. Fasino. Spectral properties of Toeplitz-plus-Hankel matrices. Calcolo, 33(1-2):87{98 (1998), 1996. Toeplitz matrices: structures, algorithms and applications (Cortona, 1996).
[17] M. Fiedler. Notes on Hilbert and Cauchy matrices. Linear Algebra Appl., 432(1):351{356, 2010.
[18] C. Garoni and S. Serra-Capizzano. Generalized locally Toeplitz sequences: theory and applications. Vol. I. Springer, Cham, 2017.
[19] G. H. Golub, F. T. Luk, and M. L. Overton. A block Lanczos method for computing the singular values of corresponding singular vectors of a matrix. ACM Trans. Math. Software, 7(2):149{169, 1981.
[20] L. Grasedyck. Singular value bounds for the cauchy matrix and solutions to sylvester equations. Technical report, Technical report 13, Germany: University Kiel, 2001.
[21] L. Grasedyck, W. Hackbusch, and S. Le Borne. Adaptive geometrically balanced clustering of H -matrices. Computing, 73(1):1{23, 2004.
[22] M. H. Gutknecht. Block krylov space methods for linear systems with multiple right-hand sides. In The Joint Workshop on Computational Chemistry and Numerical Analysis (CCNA2005), 2005.
[23] W. Hackbusch. A sparse matrix arithmetic based on H-matrices. Part I: Introduction to H-matrices. Computing, 62(2):89{108, 1999.
[24] W. Hackbusch. Hierarchical matrices: algorithms and analysis, volume 49. Springer, 2015.
[25] M. Heyouni. Extended Arnoldi methods for large low-rank Sylvester matrix equations. Appl. Numer. Math., 60(11):1171{1182, 2010.
[26] X.-Q. Jin, F.-R. Lin, and Z. Zhao. Preconditioned iterative methods for two-dimensional space-fractional di usion equations. Commun. Comput. Phys., 18(2):469{488, 2015.
[27] L. Knizhnerman and V. Simoncini. Convergence analysis of the extended Krylov subspace method for the Lyapunov equation. Numer. Math., 118(3):567{586, 2011.
[28] D. Kressner, S. Massei, and L. Robol. Low-rank updates and a divide-and-conquer method for linear matrix equations. arXiv preprint arXiv:1712.04349, 2017.
[29] S.-L. Lei and H.-W. Sun. A circulant preconditioner for fractional di usion equations. J. Comput. Phys., 242:715{725, 2013.
[30] Z. Lin and D. Wang. A nite element formulation preserving symmetric and banded di usion sti ness matrix characteristics for fractional di erential equations. Comput. Mech., pages 1{27, 2017.
[31] Y. Liu, Y. Yan, and M. Khan. Discontinuous Galerkin time stepping method for solving linear space fractional partial di erential equations. Appl. Numer. Math., 115:200{213, 2017.
[32] S. Massei, D. Palitta, and L. Robol. Solving rank structured Sylvester and Lyapunov equations. arXiv preprint arXiv:1711.05493, 2017.
[33] S. Massei and L. Robol. Hierarchical matrix toolbox. GitHub repository: https://github.com/numpi/hmtoolbox/, 2015.
[34] M. M. Meerschaert and C. Tadjeran. Finite di erence approximations for fractional advection-dispersion ow equations. J. Comput. Appl. Math., 172(1):65{77, 2004.
[35] H. Moghaderi, M. Dehghan, M. Donatelli, and M. Mazza. Spectral analysis and multigrid preconditioners for two-dimensional space-fractional di usion equations. J. Comput. Phys., 350:992{1011, 2017.
[36] J. Pan, M. Ng, and H. Wang. Fast preconditioned iterative methods for nite volume discretization of steady-state space-fractional di usion equations. Numer. Algorithms, 74(1):153{173, 2017.
[37] J. Pan, M. K. Ng, and H. Wang. Fast iterative solvers for linear systems arising from time-dependent space-fractional di usion equations. SIAM J. Sci. Comput., 38(5):A2806{A2826, 2016.
[38] H.-K. Pang and H.-W. Sun. Multigrid method for fractional di usion equations. J. Comput. Phys., 231(2):693{703, 2012.
[39] I. Podlubny. Fractional di erential equations: an introduction to fractional derivatives, fractional di erential equations, to methods of their solution and some of their applications, volume 198. Academic press, 1998.
[40] M. Raberto, E. Scalas, and F. Mainardi. Waiting-times and returns in high-frequency nancial data: an empirical study. Physica A, 314(1):749{755, 2002.
[41] J. P. Roop. Computational aspects of FEM approximation of fractional advection dispersion equations on bounded domains in R2. J. Comput. Appl. Math., 193(1):243{268, 2006.
[42] H. D. Simon and H. Zha. Low-rank matrix approximation using the Lanczos bidiagonalization process with applications. SIAM J. Sci. Comput., 21(6):2257{2274, 2000.
[43] V. Simoncini. A new iterative method for solving large-scale Lyapunov matrix equations. SIAM J. Sci. Comput., 29(3):1268{1288, 2007.
[44] W. Tian, H. Zhou, and W. Deng. A class of second order di erence approximations for solving space fractional di usion equations. Math. Comp., 84(294):1703{1727, 2015.
[45] A. Townsend. Computing with functions in two dimensions. PhD thesis, University of Oxford, 2014.
[46] A. Townsend and L. N. Trefethen. An extension of Chebfun to two dimensions. SIAM J. Sci. Comput., 35(6):C495{C518, 2013.
[47] R. Vandebril, M. Van Barel, and N. Mastronardi. Matrix computations and semiseparable matrices. Linear systems, volume 1. Johns Hopkins University Press, Baltimore, MD, 2008.
[48] H. Wang, K. Wang, and T. Sircar. A direct O(N log2 N ) nite di erence method for fractional di usion equations. J. Comput. Phys., 229(21):8095{8104, 2010.
[49] R. Wang, Y. Li, M. W. Mahoney, and E. Darve. Structured block basis factorization for scalable kernel matrix evaluation. arXiv preprint arXiv:1505.00398, 2015.
[50] J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li. Fast algorithms for hierarchically semiseparable matrices. Numer. Linear Algebra Appl., 17(6):953{976, 2010.
[51] X. Zhao, X. Hu, W. Cai, and G. E. Karniadakis. Adaptive nite element method for fractional di erential equations using hierarchical matrices. Comput. Methods Appl. Mech. Engrg., 325:56{76, 2017.
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:422761,
title = {Fast solvers for two-dimensional fractional diffusion equations using rank structured matrices},
author = {Massei S. and Mazza M. and Robol L.},
publisher = {Society for Industrial and Applied Mathematics,, Philadelphia, PA , Stati Uniti d'America},
doi = {10.1137/18m1180803 and 10.48550/arxiv.1804.05522},
journal = {SIAM journal on scientific computing (Print)},
volume = {41},
year = {2019}
}CNR authorsLaboratories
0000-0002-6545-1748
