Article Contents
Article Contents

# A preconditioned fast Hermite finite element method for space-fractional diffusion equations

• * Corresponding author: Aijie Cheng
• We develop a fast Hermite finite element method for a one-dimensional space-fractional diffusion equation, by proving that the stiffness matrix of the method can be expressed as a Toeplitz block matrix. Then a block circulant preconditioner is presented. Numerical results are presented to show the utility of the fast method.

Mathematics Subject Classification: Primary:35R11, 65N30, 65F10.

 Citation:

• Table 1.  The condition number of stiffness matrix $\mathsf{A}$ with $K=1$, $\gamma=0.5$, $\beta=0.5$

 h $2^{-8}$ $2^{-9}$ $2^{-10}$ $Cond(\mathsf{A})$ $2.329917 \times 10^{6}$ $9.320396 \times 10^{6}$ $3.728232 \times 10^{7}$

Table 2.  The $L^2$ error and $H^{1-\frac{\beta}{2}}$ error of the cubic Hermite element method with $\beta=0.1,0.5,0.9$

 $\beta$ h DOF $\|u_h - u \|_{L^2}$ order $\|u_h - u \|_{H^{1-\frac{\beta}{2}}}$ order 0.5 $2^{-3}$ 16 $4.872892 \times 10^{-4}$ $2.512934 \times 10^{-3}$ $2^{-4}$ 32 $3.573631 \times 10^{-5}$ 3.7693 $2.576521 \times 10^{-4}$ 3.2858 $2^{-5}$ 64 $2.236217 \times 10^{-6}$ 3.9982 $2.481970 \times 10^{-5}$ 3.3758 $2^{-6}$ 128 $1.342295 \times 10^{-7}$ 4.0582 $2.249708 \times 10^{-6}$ 3.4636 $2^{-7}$ 256 $7.909661 \times 10^{-9}$ 4.0849 $2.033970 \times 10^{-7}$ 3.4673 0.1 $2^{-3}$ 16 $7.851432 \times 10^{-4}$ $8.011606 \times 10^{-3}$ $2^{-4}$ 32 $6.192597 \times 10^{-5}$ 3.6643 $1.304843 \times 10^{-3}$ 2.6352 $2^{-5}$ 64 $4.208159 \times 10^{-6}$ 3.8792 $1.805192 \times 10^{-4}$ 2.8536 $2^{-6}$ 128 $2.713900 \times 10^{-7}$ 3.9547 $2.295487 \times 10^{-5}$ 2.9752 $2^{-7}$ 256 $1.794745 \times 10^{-8}$ 3.9185 $2.808095 \times 10^{-6}$ 3.0311 0.9 $2^{-3}$ 16 $3.622149 \times 10^{-4}$ $4.846137 \times 10^{-4}$ $2^{-4}$ 32 $2.767086 \times 10^{-5}$ 3.7104 $4.110739 \times 10^{-5}$ 3.5593 $2^{-5}$ 64 $1.826287 \times 10^{-6}$ 3.9213 $3.012015 \times 10^{-6}$ 3.7705 $2^{-6}$ 128 $1.180438 \times 10^{-7}$ 3.9515 $2.132241 \times 10^{-7}$ 3.8202 $2^{-7}$ 256 $7.376961 \times 10^{-9}$ 4.0001 $1.415327 \times 10^{-8}$ 3.9131

Table 3.  Performance of Gauss, CGS methods with $\beta=0.5$

 Gauss CGS h CPU(s) Itr. # CPU(s) Itr. # $2^{-6}$ 0.0916 0.2103 137 $2^{-7}$ 0.4865 1.5369 272 $2^{-8}$ 3.5858 9.8734 415 $2^{-9}$ 24.4774 62.7682 665 $2^{-10}$ 186.9874 391.5595 899 $2^{-11}$ 1485.1450 2731.0751 1676 $2^{-12}$ out of memory out of memory

Table 4.  Performance of FCGS, SFCGS and PFCGS methods with $\beta=0.5$

 FCGS SFCGS CFCGS h CPU(s) Itr. # CPU(s) Itr. # CPU(s) Itr. # $2^{-6}$ 0.0832 137 0.0305 7 0.0341 9 $2^{-7}$ 0.1809 272 0.0358 7 0.0419 10 $2^{-8}$ 0.2890 415 0.0503 7 0.0445 11 $2^{-9}$ 0.9907 665 0.0680 8 0.0653 12 $2^{-10}$ 2.4525 899 0.0932 8 0.1046 14 $2^{-11}$ 16.0752 1676 0.1536 9 0.2422 16 $2^{-12}$ 26.4751 6421 0.1914 9 0.5955 19 $2^{-13}$ N/A $>$ 30,000 0.6319 10 1.4107 22
•  T. Basu  and  H. Wang , A fast second-order finite difference method for space-fractional diffusion equations, Int. J. Numer. Anal. Mod., 9 (2012) , 658-666. D. Benson , S. W. Wheatcraft  and  M. M. Meerschaert , The fractional-order governing equation of Lévy motion, Water Resour. Res., 36 (2000) , 1413-1423.  doi: 10.1029/2000WR900032. W. Bu , Y. Tang  and  J. Yang , Galerkin finite element method for two-dimensional Riesz space fractional diffusion equations, J. Comput. Phys., 276 (2014) , 26-38.  doi: 10.1016/j.jcp.2014.07.023. R. H. Chan  and  M. K. Ng , Conjugate gradient methods for Toeplitz systems, SIAM Review, 38 (1996) , 427-482.  doi: 10.1137/S0036144594276474. R. H. Chan , Circulant preconditioners for Hermitian Toeplitz systems, SIAM Journal on Matrix Analysis and Applications, 10 (1989) , 542-550.  doi: 10.1137/0610039. R. H. Chan  and  X. Q. Jin , A family of block preconditioners for block systems, SIAM journal on scientific and statistical computing, 13 (1992) , 1218-1235.  doi: 10.1137/0913070. P. J. Davis, Circulant Matrices, Wiley-Intersciences, New York, 1979. W. Deng , Finite element method for the space and time fractional Fokker-Planck equation, SIAM Journal on Numerical Analysis, 47 (2008) , 204-226.  doi: 10.1137/080714130. K. Diethelm  and  A. D. Freed , An efficient algorithm for the evaluation of convolution integrals, Computers and Mathematics with Applications, 51 (2006) , 204-226.  doi: 10.1016/j.camwa.2005.07.010. N. Du  and  H. Wang , A fast finite element method for space-fractional dispersion equations on bounded domains in $\mathbb{R}^2$, SIAM J. Sci. Comput., 37 (2015) , A1614-A1635.  doi: 10.1137/15M1007458. V. J. Ervin  and  J. P. Roop , Variational formulation for the stationary fractional advection dispersion equation, Numer. Methods for Partial Differential Equations, 22 (2005) , 558-576.  doi: 10.1002/num.20112. V. J. Ervin  and  J. P. Roop , Variational Solution of Fractional Advection Dispersion Equations on Bounded Domains in $R^{d}$, Numer. Methods for Partial Differential Equations, 23 (2007) , 256-281.  doi: 10.1002/num.20169. R. M. Gray , Toeplitz and circulant matrices: A review, Communications and Information Theory, 2 (2016) , 155-239.  doi: 10.1561/0100000006. J. Jia  and  H. Wang , A preconditioned fast finite volume scheme for a fractional differential equation discretized on a locally refined composite mesh, J. Comput. Phys., 299 (2015) , 842-862.  doi: 10.1016/j.jcp.2015.06.028. Y. Jiang  and  X. Xu , Multigrid methods for space fractional partial differential equations, J. Comput. Phys., 302 (2015) , 374-392.  doi: 10.1016/j.jcp.2015.08.052. S. L. Lei  and  H. W. Sun , A circulant preconditioner for fractional diffusion equations, J. Comput. Phys., 242 (2013) , 715-725.  doi: 10.1016/j.jcp.2013.02.025. C. Li , Z. Zhao  and  Y. Q. Chen , Numerical approximation of nonlinear fractional differential equations with subdiffusion and superdiffusion, Computers and Mathematics with Applications, 62 (2011) , 855-875.  doi: 10.1016/j.camwa.2011.02.045. X. Li  and  C. Xu , The existence and uniqueness of the weak solution of the space-time fractional diffusion equation and a spectral method approximation, Commun. Comput. Phys., 8 (2010) , 1016-1051.  doi: 10.4208/cicp.020709.221209a. F. R. Lin , S. W. Yang  and  X. Q. Jin , Preconditioned iterative methods for fractional diffusion equation, J. Comput. Phys., 256 (2014) , 109-117.  doi: 10.1016/j.jcp.2013.07.040. Y. Lin  and  C. Xu , Finite difference/spectral approximations for the time-fractional diffusion equation, J. Comput. Phys., 225 (2007) , 1533-1552.  doi: 10.1016/j.jcp.2007.02.001. F. Liu , V. Anh  and  I. Turner , Numerical solution of the space fractional Fokker-Planck equation, J. Comput. Appl. Math., 166 (2014) , 209-219.  doi: 10.1016/j.cam.2003.09.028. C.~W. Lv  and  C. Xu , Improved error estimates of a finite difference/spectral method for time-fractional diffusion equations, Int. J. Numer. Anal. Mod., 12 (2015) , 384-400. M. M. Meerschaert , H. P. Scheffler  and  C. Tadjeran , Finite difference methods for two-dimensional fractional dispersion equation, J. Comput. Phys., 211 (2006) , 249-261.  doi: 10.1016/j.jcp.2005.05.017. M. M. Meerschaert  and  C. Tadjeran , Finite difference approximations for fractional advection-dispersion flow equations, J. Comput. Appl. Math., 172 (2004) , 65-77.  doi: 10.1016/j.cam.2004.01.033. R. Metzler  and  J. Klafter , The random walk's guide to anomalous diffusion: A fractional dynamics approach, Phys. Rep., 339 (2000) , 1-77.  doi: 10.1016/S0370-1573(00)00070-3. H. K. Pang  and  H. W. Sun , Multigrid method for fractional diffusion equations, J. Comput. Phys., 231 (2012) , 693-703.  doi: 10.1016/j.jcp.2011.10.005. I. Podlubny, Fractional Differential Equations, Academic Press, New York, 1999. Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed. , SIAM, Rhode Island, 2003. doi: 10.1137/1. 9780898718003. H. G. Sun , W. Chen  and  Y. Q. Chen , Fractional differential models for anomalous diffusion, Physica A: Statistical Mechanics and its Applications, 389 (2010) , 2719-2724.  doi: 10.1016/j.physa.2010.02.030. H. Tian , H. Wang  and  W. Q. Wang , An efficient collocation method for a non-local diffusion model, Int. J. Numer. Anal. Mod., 10 (2013) , 815-825. P. Vabishchevich , Numerical solution of nonstationary problems for a convection and a space-fractional diffusion equation, Int. J. Numer. Anal. Mod., 13 (2016) , 296-309. H. Wang  and  D. P. Yang , Wellposedness of variable-coefficient conservative fractional elliptic differential equations, SIAM Journal on Numerical Analysis, 51 (2013) , 1088-1107.  doi: 10.1137/120892295. H. Wang , D. P. Yang  and  S. F. Zhu , Accuracy of finite element methods for boundary-value problems of steady-state fractional diffusion equations, Journal of Scientific Computing, 70 (2017) , 429-449.  doi: 10.1007/s10915-016-0196-7. H. Wang  and  X. H. Zhang , A high-accuracy preserving spectral Galerkin method for the Dirichlet boundary-value problem of variable-coefficient conservative fractional diffusion equations, J. Comput. Phys., 281 (2015) , 67-81.  doi: 10.1016/j.jcp.2014.10.018. H. Wang  and  T. Basu , A fast finite difference method for two-dimensional space-fractional diffusion equations, SIAM J. Sci. Comput., 34 (2012) , A2444-A2458.  doi: 10.1137/12086491X. H. Wang  and  N. Du , A superfast-preconditioned iterative method for steady-state space-fractional diffusion equations, J. Comput. Phys., 240 (2013) , 49-57.  doi: 10.1016/j.jcp.2012.07.045. H. Wang , K. Wang  and  T. Sircar , A direct $O(N\log^2 N)$ finite difference method for fractional diffusion equations, J. Comput. Phys., 229 (2010) , 8095-8104.  doi: 10.1016/j.jcp.2010.07.011. L. L. Wei , Y. N. He  and  Y. Zhang , Numerical analysis of the fractional seventh-order KdV equation using an implicit fully discrete local discontinuous Galerkin method, Int. J. Numer. Anal. Mod., 10 (2013) , 430-444.

Tables(4)