Search

The anisotropic space-fractional diffusion equations in two dimensions are discretized by the Crank-Nicolson difference scheme with the weighted and shifted Grünwald formula, which is unconditionally stable and second-order convergence. The coefficient matrix of the discretized linear system possesses a two-level Toeplitz-like structure. Due to the anisotropy, the standard multigrid method converges slowly. By utilizing the GMRES method with a newly proposed tridiagonal preconditioner as a smoother, the convergence rate of the multigrid method can be accelerated significantly. The proposed tridiagonal preconditioner is shown to be invertible and a numerical experiment is given to demonstrate the efficiency of the proposed multigrid method with preconditioned smoother. [ABSTRACT FROM AUTHOR]

A second order alternating direction implicit scheme for time-dependent Riesz space distributed-order advection-dispersion equations is applied to higher dimensions with the Tensor-Train decomposition technique. The solutions are solved in compressed format, the Tensor-Train format, and the errors accumulated due to compressions are analyzed to ensure convergence. Problems with low-rank data are tested, the results illustrated a steeper growth in the ranks of the numerical solutions than that in related works. [ABSTRACT FROM AUTHOR]

PageRank is a widespread model for analysing the relative relevance of nodes within large graphs arising in several applications. In the current paper, we present a cost-effective Hessenberg-type method built upon the Hessenberg process for the solution of difficult PageRank problems. The new method is very competitive with other popular algorithms in this field, such as Arnoldi-type methods, especially when the damping factor is close to 1 and the dimension of the search subspace is large. The convergence and the complexity of the proposed algorithm are investigated. Numerical experiments are reported to show the efficiency of the new solver for practical PageRank computations. [ABSTRACT FROM AUTHOR]

High dimensional conservative spatial distributed-order fractional diffusion equation is discretized by midpoint quadrature rule, Crank–Nicolson method, and a finite volume approximation, with alternating direction implicit scheme. The resulting scheme is shown to be consistent and unconditionally stable, hence convergent with order 3 − α , where α is the maximum of the involving fractional orders. Moreover, if the initial condition and source term possess Tensor-Train format (TT-format) with low TT-ranks, the scheme can be solved in TT-format, such that higher dimensional cases can be considered. Perturbation analysis ensures that the accumulated errors due to data recompression do not affect the overall convergence order. Numerical examples with low TT-ranks initial conditions and source terms, and with dimensions up to 20 are tested. [ABSTRACT FROM AUTHOR]

Generally, solving linear systems from finite difference alternating direction implicit scheme of two-dimensional time-space fractional differential equations with Gaussian elimination requires O NM 1 M 2 M 1 2 + M 2 2 + N M 1 M 2 complexity and O N M 1 2 M 2 2 storage, where N is the number of temporal unknown and M1, M2 are the numbers of spatial unknown in x, y directions respectively. By exploring the structure of the coefficient matrix in fully coupled form, it possesses block lower-triangular Toeplitz structure and its blocks are block-dense Toeplitz matrices with dense-Toeplitz blocks. Based on this special structure and cooperating with time-marching or divide-and-conquer technique, two fast solvers with storage O NM 1 M 2 are developed. The complexity for the fast solver via time-marching is O NM 1 M 2 N + log M 1 M 2 and the one via divide-and-conquer technique is O NM 1 M 2 log 2 N + log M 1 M 2 . It is worth to remark that the proposed solvers are not lossy. Some discussions on achieving convergence rate for smooth and non-smooth solutions are given. Numerical results show the high efficiency of the proposed fast solvers. [ABSTRACT FROM AUTHOR]

In this article, a fast‐iterative method and a fast‐direct method is proposed for solving one‐dimensional and two‐dimensional tempered fractional diffusion equations with constant coefficients. The proposed iterative method is accelerated by circulant preconditioning which is shown to converge superlinearly while the proposed direct method is based on circulant and skew‐circulant representation for Toeplitz matrix inversion. In one‐dimensional case, the operation cost of the proposed methods are both shown to be O ( N log N ) with O ( N ) memory requirement in each time step, where N is the number of spatial nodes. With the alternating direction implicit method, it is proven that the proposed fast solution algorithms can be extended to handle two‐dimensional tempered fractional diffusion equations with O ( N 2 log N ) operation cost and O ( N 2 ) memory requirement in each time step, where the number of spatial nodes in x ‐direction and y ‐direction both equal to N . Numerical examples are provided to illustrate the effectiveness and efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

Based on the circulant-and-skew-circulant representation of Toeplitz matrix inversion and the divide-and-conquer technique, a fast numerical method is developed for solving N-by- N block lower triangular Toeplitz with M-by- M dense Toeplitz blocks system with $\mathcal {O}(MN\log N(\log N+\log M))$ complexity and $\mathcal {O}(NM)$ storage. Moreover, the method is employed for solving the linear system that arises from compact finite difference scheme for time-space fractional diffusion equations with significant speedup. Numerical examples are given to show the efficiency of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, fast numerical methods for solving space-fractional diffusion equations are studied in two stages. Firstly, a fast direct solver for an implicit finite difference scheme proposed by Haoet al.[A fourth-order approximation of fractional derivatives with its applications, J. Comput. Phys. 281 (2015), pp. 787–805], which is fourth-order accurate in space and second-order accurate in time, is developed based on a circulant-and-skew-circulant (CS) representation of Toeplitz matrix inversion. Secondly, boundary value method with spatial discretization of Haoet al.[A fourth-order approximation of fractional derivatives with its applications, J. Comput. Phys. 281 (2015), pp. 787–805] is adopted to produce a numerical solution with higher order accuracy in time. Particularly, a method with fourth-order accuracy in both space and time can be achieved. GMRES method is employed for solving the discretized linear system with two preconditioners. Based on the CS representation of Toeplitz matrix inversion, the two preconditioners can be applied efficiently, and the convergence rate of the preconditioned GMRES method is proven to be fast. Numerical examples are given to support the theoretical analysis. [ABSTRACT FROM PUBLISHER]

In this paper, high dimensional two-sided space fractional diffusion equations, derived from the fractional Fick’s law, and with monotonic variable diffusion coefficients, are solved by alternating direction implicit method. Each linear system corresponding to each spatial direction thus resulted is solved by Krylov subspace method. The method is accelerated by applying an approximate inverse preconditioner, where under certain conditions we showed that the normalized preconditioned matrix is equal to a sum of identity matrix, a matrix with small norm, and a matrix with low rank, such that the preconditioned Krylov subspace method converges superlinearly. We also briefly present some fast algorithms whose computational cost for solving the linear systems is O ( n log n ) , where n is the matrix size. The results are illustrated by some numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, a τ -preconditioner for a novel fourth-order finite difference scheme of two-dimensional Riesz space-fractional diffusion equations (2D RSFDEs) is considered, in which a fourth-order fractional centered difference operator is adopted for the discretizations of spatial Riesz fractional derivatives, while the Crank-Nicolson method is adopted to discretize the temporal derivative. The scheme is proven to be unconditionally stable and has a convergence rate of O (Δ t 2 + Δ x 4 + Δ y 4) in the discrete L 2 -norm, where Δ t , Δ x and Δ y are the temporal and spatial step sizes, respectively. In addition, the preconditioned conjugate gradient (PCG) method with τ -preconditioner is applied to solve the discretized symmetric positive definite linear systems arising from 2D RSFDEs. Theoretically, we show that the τ -preconditioner is invertible by a new technique, and analyze the spectrum of the corresponding preconditioned matrix. Moreover, since the τ -preconditioner can be diagonalized by the discrete sine transform matrix, the total operation cost of the PCG method is O (N x N y log ⁡ N x N y) , where N x and N y are the number of spatial unknowns in x - and y -directions. Finally, numerical experiments are performed to verify the convergence orders, and show that the PCG method with the τ -preconditioner for solving the discretized linear system has a convergence rate independent of discretization stepsizes. [ABSTRACT FROM AUTHOR]

An implicit second-order finite difference scheme, which is unconditionally stable, is employed to discretize fractional advection–diffusion equations with constant coefficients. The resulting systems are full, unsymmetric, and possess Toeplitz structure. Circulant and skew-circulant splitting iteration is employed for solving the Toeplitz system. The method is proved to be convergent unconditionally to the solution of the linear system. Numerical examples show that the convergence rate of the method is fast. [ABSTRACT FROM PUBLISHER]

Abstract: The implicit finite difference scheme with the shifted Grünwald formula, which is unconditionally stable, is employed to discretize fractional diffusion equations. The resulting systems are Toeplitz-like and then the fast Fourier transform can be used to reduce the computational cost of the matrix–vector multiplication. The preconditioned conjugate gradient normal residual method with a circulant preconditioner is proposed to solve the discretized linear systems. The spectrum of the preconditioned matrix is proven to be clustered around 1 if diffusion coefficients are constant; hence the convergence rate of the proposed iterative algorithm is superlinear. Numerical experiments are carried out to demonstrate that our circulant preconditioner works very well, even though for cases of variable diffusion coefficients. [Copyright &y& Elsevier]

Fractional derivatives and regime-switching models are widely used in various fields of finance because they can describe the nonlocal properties of the solutions and the changes in the market status, respectively. The regime-switching time-fractional diffusion equations that combine both advantages are also used in European option pricing; however, to our knowledge, American option pricing based on such models and their numerical methods is yet to be studied. Hence, a fast algorithm for solving the multi-state time-fractional linear complementary problem arising from the regime-switching time-fractional American option pricing models is developed in this paper. To construct the solution strategy, the original problem has been converted into a Hamilton–Jacobi–Bellman equation, and a nonlinear finite difference scheme has been proposed to discretize the problem with stability analysis. A policy-Krylov subspace method is developed to solve the nonlinear scheme. Further, to accelerate the convergence rate of the Krylov method, a tri-diagonal preconditioner is proposed with condition number analysis. Numerical experiments are presented to demonstrate the validity of the proposed nonlinear scheme and the efficiency of the proposed preconditioned policy-Krylov subspace method. [ABSTRACT FROM AUTHOR]

We consider the solution of differential equations with multidelays by using boundary value methods (BVMs). These methods require the solution of some nonsymmetric, large and sparse linear systems. The GMRES method with the Strang-type block-circulant preconditioner is proposed to solve these linear systems. If an Ak1,k2-stable BVM is used, we show that our preconditioner is invertible and the spectrum of the preconditioned matrix is clustered. It follows that when the GMRES method is applied to solving the preconditioned systems, the method would converge fast. Numerical results are given to show the effectiveness of our methods. [Copyright &y& Elsevier]

In this paper, we study nonsymmetric and highly nondiagonally dominant linear systems that arise from discretizations of constant-coefficient first-order partial differential equations (PDEs). We apply the generalized minimal residual method [Y. Saad, Iterative Methods for Sparse Linear Systems, PWS Publishing Company, Boston] for solving the system with a preconditioner based on the fast sine transform. An analytic formula for the eigenvalues of the preconditioned matrix is derived and it is shown that the eigenvalues are clustered around 1 except some outliers. The outlier eigenvalues are bounded and well separated from the origin when the size of system increases. In numerical experiments, we compare our preconditioner with the semi-Toeplitz preconditioner proposed in [SIAM J. Sci. Comput. 17 (1996) 47]. We refer to [J. Numer. Linear Algebra Appl. 1 (1992) 77, Numer. Math. J. Chinese Univ. 2 (1993) 116, BIT 32 (1992) 650, Linear Algebra Appl. 293 (1999) 85] for the early works on preconditioning techniques for PDEs. [Copyright &y& Elsevier]

To better simulate the prices of underlying assets and improve the accuracy of pricing financial derivatives, an increasing number of new models are being proposed. Among them, the Lévy process with jumps has received increasing attention because of its capacity to model sudden movements in asset prices. This paper explores the Hamilton–Jacobi–Bellman (HJB) equation with a fractional derivative and an integro-differential operator, which arise in the valuation of American options and stock loans based on the Lévy- α -stable process with jumps model. We design a fast solution strategy that includes the policy iteration method, Krylov subspace method, and banded preconditioner, aiming to solve this equation rapidly. To solve the resulting HJB equation, a finite difference method including an upwind scheme, shifted Grünwald approximation, and trapezoidal method is developed with stability and convergence analysis. Then, an algorithmic framework involving the policy iteration method and the Krylov subspace method is employed. To improve the performance of the above solver, a banded preconditioner is proposed with condition number analysis. Finally, two examples, sugar option pricing and stock loan valuation, are provided to illustrate the effectiveness of the considered model and the efficiency of the proposed preconditioned policy–Krylov subspace method. [ABSTRACT FROM AUTHOR]

Recently, fractional partial differential equations have been widely applied in option pricing problems, which better explains many important empirical facts of financial markets, but rare paper considers the multi-state options pricing problem based on fractional diffusion models. Thus, multi-state European option pricing problem under regime-switching tempered fractional partial differential equation is considered in this paper. Due to the expensive computational cost caused by the implicit finite difference scheme, a novel implicit-explicit finite difference scheme has been developed with consistency, stability, and convergence guarantee. Since the resulting coefficient matrix equals to the direct sum of several Toeplitz matrices, a preconditioned direct method has been proposed with O (S ̄ N log N + S ̄ 2 N) operation cost on each time level with adaptability analysis, where S ̄ is the number of states and N is the number of grid points. Related numerical experiments including an empirical example have been presented to demonstrate the effectiveness and accuracy of the proposed numerical method. [ABSTRACT FROM AUTHOR]

In recent years, fractional partial differential equation (FPDE) has been widely applied in options pricing problems, which better explains many important empirical facts of financial markets. However, the vast majority of the literatures focus on pricing the single asset option under the FPDE framework. In this paper, a two-dimensional FPDE governing the valuation of rainbow options is established, where two underlying assets are assumed to follow independent exponential Lévy processes, and its boundary conditions are determined by solving one-dimensional FPDEs. A second-order accurate finite difference scheme is proposed to discretize the two-dimensional FPDE. Given the block Toeplitz with Toeplitz block structure of the coefficient matrix, a fast preconditioned Krylov subspace method is developed for solving the resulting linear system with O (N log N) computational complexity per iteration, where N is the matrix size. The proposed preconditioner accelerates the convergence of the iterative method with theoretical analysis. Numerical examples are given to demonstrate the accuracy and efficiency of our proposed numerical methods. [ABSTRACT FROM AUTHOR]

In this paper, finite difference schemes for differential equations with both temporal and spatial fractional derivatives are studied. When the order of the time fractional derivative is in, an alternating direction implicit (ADI) scheme with second-order accuracy in both space and time is constructed. For equations with time fractional derivatives of order lying in, a scheme is derived and solved by the generalized minimal residual method. We also propose a preconditioner to improve the efficiency for the implementation of the scheme in this situation. [ABSTRACT FROM PUBLISHER]

• Two-dimensional distributed-order time-space fractional diffusion problem is considered and its finite difference discretization is studied. • The stability and convergence of the scheme are investigated. • The spatial second-order convergence and the temporal optimal convergence are obtained. • A fast and memory saving algorithm for solving DO time-space fractional diffusion equation is developed through Gauss quadrature formula, ESA method and PCG method. • Numerical experiments show strong effectiveness and efficiency of the method. In this paper, a fast algorithm is proposed for solving distributed-order time-space fractional diffusion equations. Integral terms in time and space directions are discretized by the Gauss-Legendre quadrature formula. The Caputo fractional derivatives are approximated by the exponential-sum-approximation method, and the finite difference method is applied for spatial approximation. The coefficient matrix of the discretized linear system is symmetric positive definite and possesses block-Toeplitz-Toeplitz-block structure. The preconditioned conjugate gradient method with a block-circulant-circulant-block preconditioner is employed to solve the linear system. Theoretically, the stability and convergence of the proposed scheme are discussed. Numerical experiments are carried out to demonstrate the effectiveness of the scheme. [ABSTRACT FROM AUTHOR]

We consider a discrete-time orthogonal spline collocation scheme for solving Schrödinger equation with wave operator. The scheme is proposed recently by Wang et al. (J Comput Appl Math 235 (2011), 1993-2005) and is showed to have high-order convergence rate when a parameter θ in the scheme is not less than \documentclass{article} \usepackage{amsmath,amsfonts, amssymb}\pagestyle{empty}\begin{document}$\frac{1}{4}$\end{document}. In this article, we show that the result can be extended to include \documentclass{article} \usepackage{amsmath,amsfonts, amssymb}\pagestyle{empty}\begin{document}$\theta\in(0,\frac{1}{4})$\end{document} under an assumption. Numerical example is given to justify the theoretical result. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013 [ABSTRACT FROM AUTHOR]

A fast preconditioned policy iteration method is proposed for the Hamilton–Jacobi–Bellman (HJB) equation involving tempered fractional order partial derivatives, governing the valuation of American options whose underlying asset follows exponential Lévy processes. An unconditionally stable upwind finite difference scheme with shifted Grünwald approximation is first developed to discretize the established HJB equation under the tempered fractional diffusion models. Next, the policy iteration method as an outer iterative method is utilized to solve the discretized HJB equation and proven to be convergent in finite steps to its numerical solution. Given the Toeplitz-like structure of the coefficient matrix in each policy iteration, the resulting linear system can be fast solved by the Krylov subspace method as an inner iterative method via fast Fourier transform (FFT). Furthermore, a novel preconditioner is proposed to speed up the convergence rate of the inner Krylov subspace iteration with theoretical analysis to ensure the linear system can be solved in O ( N log N ) operations under some mild conditions, where N is the number of spatial node points. Numerical examples are given to demonstrate the accuracy and efficiency of the proposed fast preconditioned policy method. [ABSTRACT FROM AUTHOR]

We consider high order finite difference methods for two-dimensional fractional differential equations with temporal Caputo and spatial Riemann-Liouville derivatives in this paper. We propose a scheme and show that it converges with second order in time and fourth order in space. The accuracy of our proposed method can be improved by Richardson extrapolation. Approximate solution is obtained by the generalized minimal residual (GMRES) method. A preconditioner is proposed to improve the efficiency for the implementation of the GMRES method. [ABSTRACT FROM AUTHOR]

In recent years, considerable literature has proposed the more general class of exponential Lévy processes as the underlying model for prices of financial quantities, which thus better explain many important empirical facts of financial markets. Finite moment log stable, Carr–Geman–Madan–Yor and KoBoL models are chosen from those above-mentioned models as the dynamics of underlying equity prices in this paper. With such models pricing barrier options, one kind of financial derivatives is transformed to solve specific fractional partial differential equations (FPDEs). This study focuses on numerically solving these FPDEs via the fully implicit scheme, with the shifted Grünwald approximation. The circulant preconditioned generalized minimal residual method which converges very fast with theoretical proof is incorporated for solving resultant linear systems. Numerical examples are given to demonstrate the effectiveness of the proposed preconditioner and show the accuracy of our method compared with that done by the Fourier cosine expansion method as a benchmark. [ABSTRACT FROM PUBLISHER]