Fast finite volume methods for space-fractional diffusion equations

Hong Wang; Aijie Cheng; Kaixin Wang

doi:10.3934/dcdsb.2015.20.1427

Article Contents

2015, Volume 20, Issue 5: 1427-1441. Doi: 10.3934/dcdsb.2015.20.1427

This issue Previous Article Polynomial preserving recovery of an over-penalized symmetric interior penalty Galerkin method for elliptic problems Next Article On the Benilov-Vynnycky blow-up problem

Fast finite volume methods for space-fractional diffusion equations

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

Received: September 2013

Revised: January 2015

Published: July 2015

Abstract / Introduction Related Papers Cited by

Abstract

Fractional diffusion equations model phenomena exhibiting anomalous diffusion that is characterized by a heavy tail or an inverse power law decay, which cannot be modeled accurately by second-order diffusion equations that is well known to model Brownian motions that are characterized by an exponential decay. However, fractional differential equations introduce new mathematical and numerical difficulties that have not been encountered in the context of traditional second-order differential equations. For instance, because of the nonlocal property of fractional differential operators, the corresponding numerical methods have full coefficient matrices which require storage of $O(N^2)$ and computational cost of $O(N^3)$ where $N$ is the number of grid points.
We develop a fast locally conservative finite volume method for a time-dependent variable-coefficient conservative space-fractional diffusion equation. This method requires only a computational cost of $O(N \log N)$ at each iteration and a storage of $O(N)$. Numerical experiments are presented to investigate the performance of the method and to show the strong potential of these methods.

Keywords:

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

Citation:

Related Papers

Cited by

References

[1]	R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. M. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine and H. V. der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, PA, 1994.doi: 10.1137/1.9781611971538.
[2]	T. S. Basu and H. Wang, A fast second-order finite difference method for space-fractional diffusion equations, Int'l J. Numer. Anal. Modeling, 9 (2012), 658-666.
[3]	B. Beumer, M. Kovàcs and M. M. Meerschaert, Numerical solutions for fractional reaction-diffusion equations, Computers & Mathematics with Applications, 55 (2008), 2212-2226.doi: 10.1016/j.camwa.2007.11.012.
[4]	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.
[5]	A. Böttcher and B. Silbermann, Introduction to Large Truncated Toeplitz Matrices, Springer, New York, 1999.doi: 10.1007/978-1-4612-1426-7.
[6]	M. Cui, Compact finite difference method for the fractional diffusion equation, J. Comput. Phys., 228 (2009), 7792-7804.doi: 10.1016/j.jcp.2009.07.021.
[7]	P. J. Davis, Circulant Matrices, Wiley-Intersciences, New York, 1979.
[8]	W. Deng, Finite element method for the space and time fractional Fokker-Planck equation, SIAM J. Numer. Anal., 47 (2008), 204-226.doi: 10.1137/080714130.
[9]	V. J. Ervin, N. Heuer and J. P. Roop, Numerical approximation of a time dependent, nonlinear, space-fractional diffusion equation, SIAM J. Numer. Anal., 45 (2007), 572-591.doi: 10.1137/050642757.
[10]	V. J. Ervin and J. P. Roop, Variational formulation for the stationary fractional advection dispersion equation, Numer. Methods Partial Differential Eq, 22 (2005), 558-576.doi: 10.1002/num.20112.
[11]	V. J. Ervin and J. P. Roop, Variational solution of fractional advection dispersion equations on bounded domains in $\mathbbR^d$, Numer. Methods Partial Differential Eq., 23 (2007), 256-281.doi: 10.1002/num.20169.
[12]	R. M. Gray, Toeplitz and circulant matrices: A review, Foundations and Trends in Communications and Information Theory, 2 (2006), 155-239.doi: 10.1561/0100000006.
[13]	J. Jia, C. Wang and H. Wang, A fast locally refined method for a space-fractional diffusion equation, submitted.
[14]	T. A. M. Langlands and B. I. Henry, The accuracy and stability of an implicit solution method for the fractional diffusion equation, J. Comput. Phys., 205 (2005), 719-736.doi: 10.1016/j.jcp.2004.11.025.
[15]	C. Li and F. Zeng, Finite difference methods for fractional differential equations, Int'l J. Bifurcation Chaos, 22 (2012), 1230014, 28pp.doi: 10.1142/S0218127412300145.
[16]	X. Li and C. Xu, The existence and uniqueness of the week 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.
[17]	R. Lin, F. Liu, V. Anh and I. Turner, Stability and convergence of a new explicit finite-difference approximation for the variable-order nonlinear fractional diffusion equation, Appl. Math. Comp., 212 (2009), 435-445.doi: 10.1016/j.amc.2009.02.047.
[18]	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.
[19]	F. Liu, V. Anh and I. Turner, Numerical solution of the space fractional Fokker-Planck equation, J. Comput. Appl. Math., 166 (2004), 209-219.doi: 10.1016/j.cam.2003.09.028.
[20]	F. Liu, P. Zhuang, I. Turner, K. Burrage and V. Anh, A new fractional finite volume method for solving the fractional diffusion equation, Appl. Math. Modeling, 38 (2014), 3871-3878.doi: 10.1016/j.apm.2013.10.007.
[21]	C. Lubich, Discretized fractional calculus, SIAM J. Math. Anal., 17 (1986), 704-719.doi: 10.1137/0517050.
[22]	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.
[23]	M. M. Meerschaert and C. Tadjeran, Finite difference approximations for two-sided space-fractional partial differential equations, Appl. Numer. Math., 56 (2006), 80-90.doi: 10.1016/j.apnum.2005.02.008.
[24]	R. Metler and J. Klafter, The random walk's guide to anomalous diffusion: A fractional dynamics approach, Phys. Reports, 339 (2000), 1-77.doi: 10.1016/S0370-1573(00)00070-3.
[25]	R. Metler and J. Klafter, The restaurant at the end of random walk: Recent developments in the description of anomalous transport by fractional dynamics, J. Phys. A, 37 (2004), R161-R208.doi: 10.1088/0305-4470/37/31/R01.
[26]	K. B. Oldham and J. Spanier, The Fractional Calculus, Academic Press, New York, 1974.
[27]	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.
[28]	I. Podlubny, Fractional Differential Equations, Academic Press, New York, 1999.
[29]	E. Sousa, Finite difference approximates for a fractional advection diffusion problem, J. Comput. Phys., 228 (2009), 4038-4054.doi: 10.1016/j.jcp.2009.02.011.
[30]	L. Su, W. Wang and Z. Yang, Finite difference approximations for the fractional advection diffusion equation, Physics Letters A, 373 (2009), 4405-4408.doi: 10.1016/j.physleta.2009.10.004.
[31]	C. Tadjeran and M. M. Meerschaert, A second-order accurate numerical method for the two-dimensional fractional diffusion equation, J. Comput. Phys., 220 (2007), 813-823.doi: 10.1016/j.jcp.2006.05.030.
[32]	C. Tadjeran, M. M. Meerschaert and H. P. Scheffler, A second-order accurate numerical approximation for the fractional diffusion equation, J. Comput. Phys., 213 (2006), 205-213.doi: 10.1016/j.jcp.2005.08.008.
[33]	R. S. Varga, Matrix Iterative Analysis, Second Edition, Springer-Verlag, Berlin Heideberg, 2000.doi: 10.1007/978-3-642-05156-2.
[34]	H. Wang and T. S. 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.
[35]	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.
[36]	H. Wang and N. Du, A fast finite difference method for three-dimensional time-dependent space-fractional diffusion equations and its efficient implementation, J. Comput. Phys., 253 (2013), 50-63.doi: 10.1016/j.jcp.2013.06.040.
[37]	H. Wang and N. Du, Fast alternating-direction finite difference methods for three-dimensional space-fractional diffusion equations, J. Comput. Phys., 258 (2014), 305-318.doi: 10.1016/j.jcp.2013.10.040.
[38]	H. Wang and K. Wang, An $O(N \log^2 N)$ alternating-direction finite difference method for two-dimensional fractional diffusion equations, J. Comput. Phys., 230 (2011), 7830-7839.doi: 10.1016/j.jcp.2011.07.003.
[39]	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.
[40]	H. Wang and D. Yang, Wellposedness of variable-coefficient conservative fractional elliptic differential equations, SIAM J. Numer. Anal., 51 (2013), 1088-1107.doi: 10.1137/120892295.
[41]	H. Wang, D. Yang and S. Zhu, Inhomogeneous Dirichlet boundary-value problems of space-fractional diffusion equations and their finite element approximations, SIAM J. Numer. Anal., 52 (2014), 1292-1310.doi: 10.1137/130932776.