July  2015, 20(5): 1427-1441. doi: 10.3934/dcdsb.2015.20.1427

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, China, China

Received  September 2013 Revised  January 2015 Published  May 2015

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.
Citation: Hong Wang, Aijie Cheng, Kaixin Wang. Fast finite volume methods for space-fractional diffusion equations. Discrete and Continuous Dynamical Systems - B, 2015, 20 (5) : 1427-1441. doi: 10.3934/dcdsb.2015.20.1427
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 $\mathbbmathbb{R}^{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.

show all references

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 $\mathbbmathbb{R}^{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.

[1]

Meng Zhao, Aijie Cheng, Hong Wang. A preconditioned fast Hermite finite element method for space-fractional diffusion equations. Discrete and Continuous Dynamical Systems - B, 2017, 22 (9) : 3529-3545. doi: 10.3934/dcdsb.2017178

[2]

Haili Qiao, Aijie Cheng. A fast high order method for time fractional diffusion equation with non-smooth data. Discrete and Continuous Dynamical Systems - B, 2022, 27 (2) : 903-920. doi: 10.3934/dcdsb.2021073

[3]

Abdollah Borhanifar, Maria Alessandra Ragusa, Sohrab Valizadeh. High-order numerical method for two-dimensional Riesz space fractional advection-dispersion equation. Discrete and Continuous Dynamical Systems - B, 2021, 26 (10) : 5495-5508. doi: 10.3934/dcdsb.2020355

[4]

Zheng Sun, José A. Carrillo, Chi-Wang Shu. An entropy stable high-order discontinuous Galerkin method for cross-diffusion gradient flow systems. Kinetic and Related Models, 2019, 12 (4) : 885-908. doi: 10.3934/krm.2019033

[5]

Yones Esmaeelzade Aghdam, Hamid Safdari, Yaqub Azari, Hossein Jafari, Dumitru Baleanu. Numerical investigation of space fractional order diffusion equation by the Chebyshev collocation method of the fourth kind and compact finite difference scheme. Discrete and Continuous Dynamical Systems - S, 2021, 14 (7) : 2025-2039. doi: 10.3934/dcdss.2020402

[6]

Kolade M. Owolabi, Abdon Atangana. High-order solvers for space-fractional differential equations with Riesz derivative. Discrete and Continuous Dynamical Systems - S, 2019, 12 (3) : 567-590. doi: 10.3934/dcdss.2019037

[7]

Guoshan Zhang, Peizhao Yu. Lyapunov method for stability of descriptor second-order and high-order systems. Journal of Industrial and Management Optimization, 2018, 14 (2) : 673-686. doi: 10.3934/jimo.2017068

[8]

Huan Gao, Zhibao Li, Haibin Zhang. A fast continuous method for the extreme eigenvalue problem. Journal of Industrial and Management Optimization, 2017, 13 (3) : 1587-1599. doi: 10.3934/jimo.2017008

[9]

Christos V. Nikolopoulos, Georgios E. Zouraris. Numerical solution of a non-local elliptic problem modeling a thermistor with a finite element and a finite volume method. Conference Publications, 2007, 2007 (Special) : 768-778. doi: 10.3934/proc.2007.2007.768

[10]

C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial and Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193

[11]

Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems and Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195

[12]

Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034

[13]

El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883

[14]

Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025

[15]

ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021150

[16]

Chiara Corsato, Franco Obersnel, Pierpaolo Omari, Sabrina Rivetti. On the lower and upper solution method for the prescribed mean curvature equation in Minkowski space. Conference Publications, 2013, 2013 (special) : 159-169. doi: 10.3934/proc.2013.2013.159

[17]

Kin Ming Hui, Jinwan Park. Asymptotic behaviour of singular solution of the fast diffusion equation in the punctured euclidean space. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5473-5508. doi: 10.3934/dcds.2021085

[18]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete and Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196

[19]

Moulay Rchid Sidi Ammi, Ismail Jamiai. Finite difference and Legendre spectral method for a time-fractional diffusion-convection equation for image restoration. Discrete and Continuous Dynamical Systems - S, 2018, 11 (1) : 103-117. doi: 10.3934/dcdss.2018007

[20]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete and Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184

2021 Impact Factor: 1.497

Metrics

  • PDF downloads (249)
  • HTML views (0)
  • Cited by (11)

Other articles
by authors

[Back to Top]