Search

The Crank-Nicolson (CN) method is a well-known time integrator for evolutionary partial differential equations (PDEs) arising in many real-world applications. Since the solution at any time depends on the solution at previous time steps, the CN method is inherently difficult to parallelize. In this paper, we consider a parallel method for the solution of evolutionary PDEs with the CN scheme. Using an all-at-once approach, we can solve for all time steps simultaneously using a parallelizable over time preconditioner within a standard iterative method. Due to the diagonalization of the proposed preconditioner, we can prove that most eigenvalues of preconditioned matrices are equal to 1 and the others lie in the set: $\left\{z\in\mathbb{C}: 1/(1 + \alpha) < |z| < 1/(1 - \alpha)~{\rm and}~\Re{\rm e}(z) > 0\right\}$, where $0 < \alpha < 1$ is a free parameter. Besides, the efficient implementation of the proposed preconditioner is described. Given certain conditions, we prove that the preconditioned GMRES method exhibits a mesh-independent convergence rate. Finally, we will verify both theoretical findings and the efficacy of the proposed preconditioner via numerical experiments on financial option pricing PDEs., Comment: 18 pages, 5 figures and 4 tables (update some contexts)

Damped wave equations have been used in many real-world fields. In this paper, we study a low-rank solution of the strongly damped wave equation with the damping term, visco-elastic damping term and mass term. Firstly, a second-order finite difference method is employed for spatial discretization. Then, we receive a second-order matrix differential system. Next, we transform it into an equivalent first-order matrix differential system, and split the transformed system into three subproblems. Applying a Strang splitting to these subproblems and combining a dynamical low-rank approach, we obtain a low-rank algorithm. Numerical experiments are reported to demonstrate that the proposed low-rank algorithm is robust and accurate, and has second-order convergence rate in time., Comment: 14 pages, 3 figures, 2 tables

The Black-Scholes (B-S) equation has been recently extended as a kind of tempered time-fractional B-S equations, which becomes an interesting mathematical model in option pricing. In this study, we provide a fast numerical method to approximate the solution of the tempered time-fractional B-S model. To achieve high-order accuracy in space and overcome the weak initial singularity of exact solution, we combine the compact difference operator with L1-type approximation under nonuniform time steps to yield the numerical scheme. The convergence of the proposed difference scheme is proved to be unconditionally stable. Moreover, the kernel function in the tempered Caputo fractional derivative is approximated by sum-of-exponentials, which leads to a fast unconditionally stable compact difference method that reduces the computational cost. Finally, numerical results demonstrate the effectiveness of the proposed methods., Comment: 26 pages, 4 tables and 3 figures; correct and make some sentences clear. Ver3: deeply revise and reconstruct the context in order to make it more concise

The extended Fisher--Kolmogorov (EFK) equation has been used to describe some phenomena in physical, material and biology systems. In this paper, we propose a full-rank splitting scheme and a rank-adaptive splitting approach for this equation. We first use a finite difference method to approximate the space derivatives. Then, the resulting semi-discrete system is split into two stiff linear parts and a nonstiff nonlinear part. This leads to our full-rank splitting scheme. The convergence and the maximum principle of the proposed scheme are proved rigorously. Based on the frame of the full-rank splitting scheme, a rank-adaptive splitting approach for obtaining a low-rank solution of the EFK equation. Numerical examples show that our methods are robust and accurate. They can also preserve energy dissipation and the discrete maximum principle., Comment: 17pages, 4 figures, 4 tables

Time-space fractional Bloch-Torrey equations (TSFBTEs) are developed by some researchers to investigate the relationship between diffusion and fractional-order dynamics. In this paper, we first propose a second-order implicit difference scheme for TSFBTEs by employing the recently proposed L2-type formula [A.~A.~Alikhanov, C.~Huang, Appl.~Math.~Comput.~(2021) 126545]. Then, we prove the stability and the convergence of the proposed scheme. Based on such a numerical scheme, an L2-type all-at-once system is derived. In order to solve this system in a parallel-in-time pattern, a bilateral preconditioning technique is designed to accelerate the convergence of Krylov subspace solvers according to the special structure of the coefficient matrix of the system. We theoretically show that the condition number of the preconditioned matrix is uniformly bounded by a constant for the time fractional order $\alpha \in (0,0.3624)$. Numerical results are reported to show the efficiency of our method., Comment: 25 pages, 6 tables, 4 figures

The space fractional Cahn-Hilliard phase-field model is more adequate and accurate in the description of the formation and phase change mechanism than the classical Cahn-Hilliard model. In this article, we propose a temporal second-order energy stable scheme for the space fractional Cahn-Hilliard model. The scheme is based on the second-order backward differentiation formula in time and a finite difference method in space. Energy stability and convergence of the scheme are analyzed, and the optimal convergence orders in time and space are illustrated numerically. Note that the coefficient matrix of the scheme is a $2 \times 2$ block matrix with a Toeplitz-like structure in each block. Combining the advantages of this special structure with a Krylov subspace method, a preconditioning technique is designed to solve the system efficiently. Numerical examples are reported to illustrate the performance of the preconditioned iteration., Comment: 26 pages, 5 tables, 4 figures

Fractional Ginzburg-Landau equations as the generalization of the classical one have been used to describe various physical phenomena. In this paper, we propose a numerical integration method for solving space fractional Ginzburg-Landau equations based on a dynamical low-rank approximation. We first approximate the space fractional derivatives by using a fractional centered difference method. Then, the resulting matrix differential equation is split into a stiff linear part and a nonstiff (nonlinear) one. For solving these two subproblems, a dynamical low-rank approach is used. The convergence of our method is proved rigorously. Numerical examples are reported which show that the proposed method is robust and accurate., Comment: 17 pages; 3 figures; 4 tables

Volterra subdiffusion problems with weakly singular kernel describe the dynamics of subdiffusion processes well.The graded $L1$ scheme is often chosen to discretize such problems since it can handle the singularity of the solution near $t = 0$. In this paper, we propose a modification. We first split the time interval $[0, T]$ into $[0, T_0]$ and $[T_0, T]$, where $T_0$ ($0 < T_0 < T$) is reasonably small. Then, the graded $L1$ scheme is applied in $[0, T_0]$, while the uniform one is used in $[T_0, T]$. Our all-at-once system is derived based on this strategy. In order to solve the arising system efficiently, we split it into two subproblems and design two preconditioners. Some properties of these two preconditioners are also investigated. Moreover, we extend our method to solve semilinear subdiffusion problems. Numerical results are reported to show the efficiency of our method., Comment: 3 figures; 3 tables. This preprint has been accepted by Journal of Scientific Computing

In this paper, fast numerical methods are established for solving a class of time distributed-order and Riesz space fractional diffusion-wave equations. We derive new difference schemes by the weighted and shifted Gr$\ddot{\rm{u}}$nwald formula in time and the fractional centered difference formula in space. The unconditional stability and second-order convergence in time, space and distributed-order of the difference schemes are analyzed. In the one-dimensional case, the Gohberg-Semencul formula utilizing the preconditioned Krylov subspace method is developed to solve the symmetric positive definite Toeplitz linear systems derived from the proposed difference scheme. In the two-dimensional case, we also design a global preconditioned conjugate gradient method with a truncated preconditioner to solve the discretized Sylvester matrix equations. We prove that the spectrums of the preconditioned matrices in both cases are clustered around one, such that the proposed numerical methods with preconditioners converge very quickly. Some numerical experiments are carried out to demonstrate the effectiveness of the proposed difference schemes and show that the performances of the proposed fast solution algorithms are better than other numerical methods., Comment: 36 pages, 7 figures, 12 tables

The $p$-step backwards difference formula (BDF) for solving the system of ODEs can result in a kind of all-at-once linear systems, which are solved via the parallel-in-time preconditioned Krylov subspace solvers (see McDonald, Pestana, and Wathen [SIAM J. Sci. Comput., 40(2) (2018): A1012-A1033] and Lin and Ng [arXiv:2002.01108, 17 pages]. However, these studies ignored that the $p$-step BDF ($p\geq 2$) is not selfstarting, when they are exploited to solve time-dependent PDEs. In this note, we focus on the 2-step BDF which is often superior to the trapezoidal rule for solving the Riesz fractional diffusion equations, but its resultant all-at-once discretized system is a block triangular Toeplitz system with a low-rank perturbation. Meanwhile, we first give an estimation of the condition number of the all-at-once systems and then adapt the previous work to construct two block circulant (BC) preconditioners. Both the invertibility of these two BC preconditioners and the eigenvalue distributions of preconditioned matrices are discussed in details. The efficient implementation of these BC preconditioners is also presented especially for handling the computation of dense structured Jacobi matrices. Finally, numerical experiments involving both the one- and two-dimensional Riesz fractional diffusion equations are reported to support our theoretical findings., Comment: 18 pages. 2 figures. 6 Table. Tech. Rep.: Institute of Mathematics, Southwestern University of Finance and Economics. Revised-1: refine/shorten the contexts and correct some typos; Revised-2: correct some references. Accepted by {\em Numer. Math. Theor. Meth. Appl.}, 14 Mar. 2021

In this paper, we develop two fast implicit difference schemes for solving a class of variable-coefficient time-space fractional diffusion equations with integral fractional Laplacian (IFL). The proposed schemes utilize the graded $L1$ formula for the Caputo fractional derivative and a special finite difference discretization for IFL, where the graded mesh can capture the model problem with a weak singularity at initial time. The stability and convergence are rigorously proved via the $M$-matrix analysis, which is from the spatial discretized matrix of IFL. Moreover, the proposed schemes use the fast sum-of-exponential approximation and Toeplitz matrix algorithms to reduce the computational cost for the nonlocal property of time and space fractional derivatives, respectively. The fast schemes greatly reduce the computational work of solving the discretized linear systems from $\mathcal{O}(MN^3 + M^2N)$ by a direct solver to $\mathcal{O}(MN(\log N + N_{exp}))$ per preconditioned Krylov subspace iteration and a memory requirement from $O(MN^2)$ to $O(NN_{exp})$, where $N$ and $(N_{exp} \ll)~M$ are the number of spatial and temporal grid nodes. The spectrum of preconditioned matrix is also given for ensuring the acceleration benefit of circulant preconditioners. Finally, numerical results are presented to show the utility of the proposed methods., Comment: 31pages, 11 tables, 4 figures. Version4: accepted for publication by Mathematical Methods in Applied Sciences

In this paper, we first propose an unconditionally stable implicit difference scheme for solving generalized time-space fractional diffusion equations (GTSFDEs) with variable coefficients. The numerical scheme utilizes the $L1$-type formula for the generalized Caputo fractional derivative in time discretization and the second-order weighted and shifted Gr\"{u}nwald difference (WSGD) formula in spatial discretization, respectively. Theoretical results and numerical tests are conducted to verify the $(2 - \gamma)$-order and 2-order of temporal and spatial convergence with $\gamma\in(0,1)$ the order of Caputo fractional derivative, respectively. The fast sum-of-exponential approximation of the generalized Caputo fractional derivative and Toeplitz-like coefficient matrices are also developed to accelerate the proposed implicit difference scheme. Numerical experiments show the effectiveness of the proposed numerical scheme and its good potential for large-scale simulation of GTSFDEs., Comment: 23 pages, 10 tables, 1 figure. Make several corrections again and have been submitted to a journal at Sept. 20, 2019. Version 2: Make some necessary corrections and symbols, 13 Jan. 2020. Revised manuscript has been resubmitted to journal

A kind of spatial fractional diffusion equations in this paper are studied. Firstly, an L1 formula is employed for the spatial discretization of the equations. Then, a second order scheme is derived based on the resulting semi-discrete ordinary differential system by using the implicit integration factor method, which is a class of efficient semi-implicit temporal scheme. Numerical results show that the proposed scheme is accurate even for the discontinuous coefficients., Comment: 7 pages, 1 figure and 4 tables. This paper is accepted by the Second International Conference on Physics, Mathematics and Statistics. It will be published in Journal of Physics: Conference Series

An all-at-once linear system arising from the nonlinear tempered fractional diffusion equation with variable coefficients is studied. Firstly, the nonlinear and linearized implicit schemes are proposed to approximate such the nonlinear equation with continuous/discontinuous coefficients. The stabilities and convergences of the two schemes are proved under several suitable assumptions, and numerical examples show that the convergence orders of these two schemes are $1$ in both time and space. Secondly, a nonlinear all-at-once system is derived based on the nonlinear implicit scheme, which may suitable for parallel computations. Newton's method, whose initial value is obtained by interpolating the solution of the linearized implicit scheme on the coarse space, is chosen to solve such the nonlinear all-at-once system. To accelerate the speed of solving the Jacobian equations appeared in Newton's method, a robust preconditioner is developed and analyzed. Numerical examples are reported to demonstrate the effectiveness of our proposed preconditioner. Meanwhile, they also imply that such the initial guess for Newton's method is more suitable., Comment: 10 tables, 2 figures

The aim of this paper is to develop fast second-order accurate difference schemes for solving one- and two-dimensional time distributed-order and Riesz space fractional diffusion equations. We adopt the same measures for one- and two-dimensional problems as follows: we first transform the time distributed-order fractional diffusion problem into the multi-term time-space fractional diffusion problem with the composite trapezoid formula. Then, we propose a second-order accurate difference scheme based on the interpolation approximation on a special point to solve the resultant problem. Meanwhile, the unconditional stability and convergence of the new difference scheme in $L_2$-norm are proved. Furthermore, we find that the discretizations lead to a series of Toeplitz systems which can be efficiently solved by Krylov subspace methods with suitable circulant preconditioners. Finally, numerical results are presented to show the effectiveness of the proposed difference methods and demonstrate the fast convergence of our preconditioned Krylov subspace methods., Comment: 37 pages, 6 figures, 8 tables

A block lower triangular Toeplitz system arising from time-space fractional diffusion equation is discussed. For efficient solutions of such the linear system, the preconditioned biconjugate gradient stabilized method and flexible general minimal residual method are exploited. The main contribution of this paper has two aspects: (i) A block bi-diagonal Toeplitz preconditioner is developed for the block lower triangular Toeplitz system, whose storage is of $\mathcal{O}(N)$ with $N$ being the spatial grid number; (ii) A new skew-circulant preconditioner is designed to fast calculate the inverse of the block bi-diagonal Toeplitz preconditioner multiplying a vector. Numerical experiments are given to demonstrate the efficiency of our preconditioners., Comment: 19 pages, 3 figures, 5 table

An implicit finite difference scheme based on the $L2$-$1_{\sigma}$ formula is presented for a class of one-dimensional time fractional reaction-diffusion equations with variable coefficients and time drift term. The unconditional stability and convergence of this scheme are proved rigorously by the discrete energy method, and the optimal convergence order in the $L_2$-norm is $\mathcal{O}(\tau^2 + h^2)$ with time step $\tau$ and mesh size $h$. Then, the same measure is exploited to solve the two-dimensional case of this problem and a rigorous theoretical analysis of the stability and convergence is carried out. Several numerical simulations are provided to show the efficiency and accuracy of our proposed schemes and in the last numerical experiment of this work, three preconditioned iterative methods are employed for solving the linear system of the two-dimensional case., Comment: 27 pages, 5 figures, 5 tables

In this paper, we consider a fast and second-order implicit difference method for approximation of a class of time-space fractional variable coefficients advection-diffusion equation. To begin with, we construct an implicit difference scheme, based on $L2-1_{\sigma}$ formula [A. A. Alikhanov, A new difference scheme for the time fractional diffusion equation, \emph{J. Comput. Phys.}, 280 (2015)] for the temporal discretization and weighted and shifted Gr\"{u}nwald method for the spatial discretization. Then, unconditional stability of the implicit difference scheme is proved, and we theoretically and numerically show that it converges in the $L_2$-norm with the optimal order $\mathcal{O}(\tau^2 + h^2)$ with time step $\tau$ and mesh size $h$. Secondly, three fast Krylov subspace solvers with suitable circulant preconditioners are designed to solve the discretized linear systems with the Toeplitz matrix. In each iterative step, these methods reduce the memory requirement of the resulting linear equations from $\mathcal{O}(N^2)$ to $\mathcal{O}(N)$ and the computational complexity from $\mathcal{O}(N^3)$ to $\mathcal{O}(N \log N)$, where $N$ is the number of grid nodes. Finally, numerical experiments are carried out to demonstrate that these methods are more practical than the traditional direct solvers of the implicit difference methods, in terms of memory requirement and computational cost., Comment: 31 pages,12 tables,8 figures. arXiv admin note: text overlap with arXiv:1510.05089 by other authors