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

Meng Zhao; Aijie Cheng; Hong Wang

doi:10.3934/dcdsb.2017178

Article Contents

2017, Volume 22, Issue 9: 3529-3545. Doi: 10.3934/dcdsb.2017178

This issue Previous Article On stochastic multi-group Lotka-Volterra ecosystems with regime switching Next Article Time-periodic and stable patterns of a two-competing-species Keller-Segel chemotaxis model: Effect of cellular growth

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

1.
School of Mathematics, Shandong University, Jinan, Shandong 250100, China
2.
Department of Mathematics, University of South Carolina, Columbia, SC 29208, USA

* Corresponding author: Aijie Cheng
* Corresponding author: Aijie Cheng

Received: August 2016

Revised: April 2017

Published: October 2017

Abstract / Introduction Full Text(HTML) Figure(0) / Table(4) Related Papers Cited by

Abstract

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.

Keywords:

Anomalous diffusion,
space-fractional diffusion equation,
hermite finite element,
block Toeplitz matrix,
fast Fourier transform,
preconditioned conjugate gradient squared method.

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

Citation:

Full Text(HTML)

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}$

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

	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.