Search

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]

We present a red–black skewed extrapolation cascadic multigrid (SkECMG) method to solve the Poisson equation in two dimensions based on the modified standard and skewed five-point finite difference discretization. With the help of the extrapolation technique, we develop a new extrapolation operator. Applying this proposed extrapolation operator for the second-order finite difference solutions on the current and previous coarse grid, we can design a fourth-order initial value for the iterative solver on the next finer grid. The red–black Gauss–Seidel method is adopted as a smoother which is conducive to parallel implementation. Moreover, we discuss a new sifting method as a stopping criterion to reduce the number of smoothing iterations. The numerical experiment is conducted on the square domain to verify that our SkECMG algorithm can achieve high efficiency and keep less cost simultaneously. [ABSTRACT FROM AUTHOR]

In this paper, a fast and memory-saving numerical scheme is presented for solving hidden-memory variable-order time-fractional diffusion equations based on the L1 method. Due to the nonlocality of fractional operators, the L1 method leads to a high computational complexity. To reduce the storage and computational cost, a modified exponential-sum-approximation method is utilized to approximate the convolution kernel involved in the fractional derivative. Additionally, one of the challenges faced during theoretical analysis is the loss of monotonicity of the temporal discretization coefficients caused by the hidden-memory variable order. A pioneering decomposition technique has been adopted to address this. The scheme has been theoretically proven to be convergent, and its effectiveness and accuracy have been confirmed through numerical examples. [ABSTRACT FROM AUTHOR]

A divide-and-conquer solver coupled with Tensor-Train (TT) format is proposed for solving the d-dimensional time-space fractional diffusion equations with alternating direction implicit finite difference scheme. In contrast to the complexity and storage of divide-and-conquer solver in full storage format, which grows at least exponentially with dimension d, complexity and storage of the proposed solver are O N M log M + r r + (d - 1) r 2 + N log 2 N · r and O M r + (d - 1) r 2 + N r with acceleration by an efficient approximated Toeplitz inversion, where M, N are numbers of spatial and temporal grid points and r is the TT-ranks of related TT format data. Hence they grow slowly with dimension d if the TT-ranks r is low. For reducing the increase of TT-ranks after certain TT operations, TT rounding is performed with introduced error, which is analyzed for giving a criterion for preserving convergence rate of the numerical scheme. The accuracy and efficiency of the proposed solver is illustrated by numerical experiments with dimension d up to 20 for case of low TT-ranks initial conditions and source terms. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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 paper, a first order implicit finite difference scheme with Krylov subspace linear system solver is employed to solving time-dependent space-fractional diffusion equations in high dimensions where the initial condition and source term are in tensor-train (TT) format with low TT-ranks. In the time-marching process, TT-format of the solution is maintained and the increment of TT-ranks due to addition is moderated by rounding. The error introduced by rounding is shown to be consistent with the first order finite difference scheme. On the other hand, the linear systems involved in the solution process are shown to possess Toeplitz-like structure so that the complexity and required memory for Krylov subspace solver can be optimized. Further reduction in complexity is made by utilizing a circulant preconditioner which accelerates the convergence rate of Krylov subspace method dramatically. Numerical examples for problems up to 20 dimensions are presented. [ABSTRACT FROM AUTHOR]

Preconditioners are popularly used for speeding up Krylov subspace iterative method for solving linear systems from discretization of fractional differential equations (FDEs) on rectangular domains. Though some recent works have been developed for FDEs in general convex domains, it still has room for improvement in the design of preconditioner. For this sake, in this paper, we theoretically study the preconditioner problem for two-dimensional conservative space-fractional diffusion equations with variable coefficients and propose a robust preconditioner with penalty term which can deal with any convex domains significantly. We further prove that the proposed preconditioner equals to the coefficient matrix plus a low rank matrix and a matrix with small norm under certain conditions. It implies that the new preconditioner can effectively accelerate the convergence rate of Krylov subspace method. Experimental results show the good performance of the robust preconditioner. [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]

A fast preconditioned penalty method is developed for a system of parabolic linear complementarity problems (LCPs) involving tempered fractional order partial derivatives governing the price of American options whose underlying asset follows a geometry Lévy process with multi-state regime switching. By means of the penalty method, the system of LCPs is approximated with a penalty term by a system of nonlinear tempered fractional partial differential equations (TFPDEs) coupled by a finite-state Markov chain. The system of nonlinear TFPDEs is discretized with the shifted Grünwald approximation by an upwind finite difference scheme which is shown to be unconditionally stable. Semi-smooth Newton’s method is utilized to solve the finite difference scheme as an outer iterative method in which the Jacobi matrix is found to possess Toeplitz-plus-diagonal structure. Consequently, 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. With the above-mentioned preconditioning technique via FFT, under some mild conditions, the operation cost in each Newton’s step can be expected to be O(NlogN), where N is the size of the coefficient matrix. Numerical examples are given to demonstrate the accuracy and efficiency of our proposed fast preconditioned penalty method. [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]

Circulant and skew-circulant splitting iteration method is employed for solving linear systems from finite difference discretisation of tempered fractional diffusion equations. The method is shown to be convergent unconditionally and the convergence rate is fast in numerical tests. In each iteration, a circulant system and a skew-circulant system are required to be solved which cost only $$O(N\log N)$$ operations by fast Fourier transform, where N is the number of interior mesh points in space. Moreover, the induced preconditioner possesses circulant-times-skew-circulant structure so that it can be inverted in $$O(N\log N)$$ operation. In all of our numerical experiments, the preconditioner performs very well with a very simple choice of the method parameter. [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 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]

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]

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]

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]