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.
Bibliographical noteFunding Information:
\ast Submitted to the journal's Methods and Algorithms for Scientific Computing section April 16, 2018; accepted for publication (in revised form) May 17, 2019; published electronically August 22, 2019. https://doi.org/10.1137/18M1180803 Funding: This work was supported by an INdAM/GNCS project. The work of the first author has been supported by the SNSF research project Fast algorithms from low-rank updates, grant: 200020 178806. The work of the third author was supported by the Region of Tuscany (PAR-FAS 2007-2013) and by MIUR, the Italian Ministry of Education, Universities and Research (FAR) within the Call FAR-FAS 2014 (MOSCARDO Project: ICT technologies for structural monitoring of age-old constructions based on wireless sensor networks and drones, 2016--2018). \dagger EPF Lausanne, Switzerland (firstname.lastname@example.org).
© 2019 Society for Industrial and Applied Mathematics.
Copyright 2019 Elsevier B.V., All rights reserved.
- Fractional diffusion
- Fractional operators
- Hierarchical matrices
- Structured matrices
- Sylvester equation