Search

SUMMARY A fast exponential time integration scheme is considered for pricing European and double barrier options in jump-diffusion models. After spatial discretization, the option pricing problem is transformed into the product of a matrix exponential and a vector, while the matrix bears a Toeplitz structure. The shift-and-invert Arnoldi method is then employed for fast approximation to such operation. Owing to the Toeplitz structure, the computational cost can be reduced by the fast Fourier transform. Furthermore, the discretized form of option pricing problem satisfies a given condition such that the error bound of the shift-and-invert Arnoldi approximation is unrelated to the norm of the matrix. Numerical tests are carried out to compare the proposed method with other option pricing methods. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The Lanczos method with shift-invert technique is exploited to approximate the symmetric positive semidefinite Toeplitz matrix exponential. The complexity is lowered by the Gohberg-Semencul formula and the fast Fourier transform. Application to the numerical solution of an integral equation is studied. Numerical experiments are carried out to demonstrate the effectiveness of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We study the solutions of block Toeplitz systems A[sub mn]u = b by the multigrid method (MGM). Here the block Toeplitz matrices A[sub mn] are generated by a nonnegative func- tion f(x,y) with zeros. Since the matrices A[sub mn] are ill-conditioned, the convergence factor of classical iterative methods will approach i as the size of the matrices becomes large. These classical methods, therefore, are not applicable for solving ill-conditioned systems. The MGM is then proposed in this paper. For a class of block Toeplitz matrices, we show that the convergence factor of the two-grid method (TGM) is uniformly bounded below i independent of mn and the full MGM has convergence factor depending only on the number of levels. The cost per iteration for the MGM is of O(mn log mn) operations. Numerical results are given to explain the convergence rate. [ABSTRACT FROM AUTHOR]

In this paper, we consider solving non-convolution type integral equations by the preconditioned conjugate gradient method. The fast dense matrix method is a fast multiplication scheme that provides a dense discretization matrix A approximating a given integral equation. The dense matrix A can be constructed in O(n) operations and requires only O(n) storage where n is the size of the matrix. Moreover, the matrix-vector multiplication Ax can be done in O(n log n) operations. Thus if the conjugate gradient method is used to solve the discretized system, the cost per iteration is O(n log n) operations. However, for some integral equations, such as the Fredholm integral equations of the first kind, the system will be ill-conditioned and therefore the convergence rate of the method will be slow. In these cases, preconditioning is required to speed up the convergence rate of the method. A good choice of preconditioner is the optimal circulant preconditioner which is the minimizer of C — A[sub F] in Frobenius norm over all circulant matrices C. It can be obtained by taking arithmetic averages of all the entries of A and therefore the cost of constructing the preconditioner is of O(n²) operations for general dense matrices. In this paper, we develop an O(n log n) method of constructing the preconditioner for dense matrices A obtained from the fast dense matrix method. Application of these ideas to boundary integral equations from potential theory will be given. These equations are ill-conditioned whereas their optimal circulant preconditioned equations will be well-conditioned. The accuracy of the approximation A, the fast construction of the preconditioner and the fast convergence of the preconditioned systems will be illustrated by numerical examples. [ABSTRACT FROM AUTHOR]

Summary: In this paper, we study the original Meyer model of cartoon and texture decomposition in image processing. The model, which is a minimization problem, contains an l1‐based TV‐norm and an l∞‐based G‐norm. The main idea of this paper is to use the dual formulation to represent both TV‐norm and G‐norm. The resulting minimization problem of the Meyer model can be given as a minimax problem. A first‐order primal‐dual algorithm can be developed to compute the saddle point of the minimax problem. The convergence of the proposed algorithm is theoretically shown. Numerical results are presented to show that the original Meyer model can decompose better cartoon and texture components than the other testing methods. [ABSTRACT FROM AUTHOR]

When one approximates elliptic equations by the spectral collocation method on the Chebyshev-Gauss-Lobatto (CGL) grid, the resulting coefficient matrix is dense and ill-conditioned. It is known that a good preconditioner, in the sense that the preconditioned system becomes well conditioned, can be constructed with finite difference on the CGL grid. However, there is a lack of an efficient solver for this preconditioner in multi-dimension. A modified preconditioner based on the approximate inverse technique is constructed in this paper. The computational cost of each iteration in solving the preconditioned system is O(ℓNxNy logNx), where Nx,Ny are the grid sizes in each direction and ℓ is a small integer. Numerical examples are given to demonstrate the efficiency of the proposed preconditioner. [ABSTRACT FROM AUTHOR]

In this paper, we study a V-cycle multigrid method for linear systems arising from time-dependent two-dimensional space-fractional diffusion equations. The coefficient matrices of the linear systems are structured such that their matrix-vector multiplications can be computed efficiently. The main advantage using the multigrid method is to handle the space-fractional diffusion equations on non-rectangular domains, and to solve the linear systems with non-constant coefficients more effectively. The main idea of the proposed multigrid method is to employ two banded splitting iteration schemes as pre-smoother and post-smoother. The pre-smoother and the post-smoother take banded splitting of the coefficient matrix under the x -dominant ordering and the y -dominant ordering, respectively. We prove the convergence of the proposed two banded splitting iteration schemes in the sense of infinity norm. Results of numerical experiments for time-dependent two-dimensional space-fractional diffusion equations on rectangular, L-shape and U-shape domains are reported to demonstrate that both computational time and iteration number required by the proposed method are significantly smaller than those of the other tested methods. [ABSTRACT FROM AUTHOR]

Combining the scale auxiliary variable (SAV) approach with leapfrog finite difference methods, an unconditional energy-stable, non-couple and linearly implicit numerical scheme is presented for solving spatial fractional Cahn–Hilliard equations. The fully-discrete scheme gives an indefinite and ill-conditioned system of linear algebraic equations, whose coefficient matrix is a 2 × 2 block with block Toeplitz matrix. The preconditioned minimum residual method with a positive preconditioner is employed for the resulting system. Numerical results are presented to confirm the effectiveness of the proposed numerical scheme and preconditioner. [ABSTRACT FROM AUTHOR]

In this paper, we study a τ-preconditioner for non-symmetric linear system arising from a steady-state multi-dimensional Riemann-Liouville (RL) fractional diffusion equation. The generalized minimal residual (GMRES) method is applied to solve the preconditioned linear system. Theoretically, we show that the GMRES solver for the preconditioned linear system has a convergence rate independent of discretization stepsizes. To the best of our knowledge, this is the first iterative solver with stepsize-independent convergence rate for the non-symmetric linear system. The proposed τ-preconditioner is diagonalizable by the sine transform matrix, thanks to which the matrix-vector multiplication in each iteration step can be fast implemented by the fast sine transform (FST). Hence, the total operation cost of the proposed solver for the non-symmetric problem is linearithmic. Numerical results are reported to show the efficiency of the proposed preconditioner. [ABSTRACT FROM AUTHOR]

• What Is New of This Paper In this paper, sixth-order QCD schemes are proposed to solve the boundary value problems of multi-dimensional Helmholtz equations with variable wavenumber. To the best of our knowledge, there were no any explicit sixth-order compact difference schemes without containing the derivatives of given functions whose global convergence order can be theoretically guaranteed in the meantime. • Significance of This Paper In this paper, sixth-order QCD schemes are constructed to solve the boundary value problems of two-dimensional and three-dimensional Helmholtz equations with variable wavenumber. Our strategy is to discretize the equation by the fourth-order compact scheme at the improper interior grid points that adjoin the boundary, while the sixth-order scheme, where it is compact only for the unknowns, is exploited to the proper interior grid points that are without adjoining the boundary. Different from the classic sixth-order schemes in the literature, this treatment makes the proposed schemes only require the values of source term and wavenumber on the grid points instead of the derivatives of given functions. Theoretically, we prove the QCD schemes can achieve global sixth-order accuracy for non-positive constant wavenumber. Finally, numerical experiments are carried out to manifest the accuracy and convergence order of proposed numerical methods for general wavenumber. • Highlights Sixth-order QCD schemes are constructed to solve multi-dimensional Helmholtz equations with variable wavenumber. The proposed schemes do not contain the derivatives of given functions and without involving the additional calculation of the second boundary layer for unknowns. Theoretically, we prove the QCD schemes can achieve the global sixth-order accuracy. Sixth-order quasi-compact difference (QCD) schemes are proposed for the two-dimensional (2D) and the three-dimensional (3D) Helmholtz equations with the variable parameter. Our approach provides the compact mesh stencil for the unknowns, while the noncompact mesh stencil is employed for the source term and the parameter function without involving their derivatives. For the proper interior grid points that are without adjoining the boundary, the sixth-order truncated errors are obtained by the QCD method. Yet the compact scheme is utilized for both of the source term and the parameter function on the improper interior grids that neighbor the boundary, which only reaches the fourth-order local truncated errors. Theoretically, the sixth-order accuracy of the global error by the proposed QCD method is strictly proved for the non-positive constant parameter. Numerical examples are given to demonstrate that the QCD method achieves the global sixth-order convergence for general variable parameters. [ABSTRACT FROM AUTHOR]

• 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]

In this paper, we study the numerical solution for the evolutionary stable distribution (ESD) model. A new implicit–explicit scheme is proposed to discretize the ESD model, which can keep the numerical solution unconditionally positive at each time step. Moreover, it is theoretically proved that the proposed scheme satisfies the property of the entropy dissipation. Numerical experiments are carried out to demonstrate the numerical accuracy and the effectiveness of the proposed scheme. • A new implicit–explicit scheme is proposed to discretize the evolutionary stable distribution model. • Theoretically, it is proved that the proposed scheme satisfies the property of the entropy dissipation. • Numerical experiments are carried out to demonstrate the effectiveness of the proposed scheme. [ABSTRACT FROM AUTHOR]