Shift‐invert Lanczos method for the symmetric positive semidefinite Toeplitz matrix exponential

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.     

Rational Krylov methods in exponential integrators for European option pricing

The aim of this paper is to analyze efficient numerical methods for time integration of European option pricing models. When spatial discretization is adopted, the resulting problem consists of an ordinary differential equation that can be approximated by means of exponential Runge–Kutta integrators, where the matrix‐valued functions are computed by the so‐called shift‐and‐invert Krylov method. To our knowledge, the use of this numerical approach is innovative in the framework of option pricing, and it reveals to be very attractive and efficient to solve the problem at hand. In this respect, we propose some a posteriori estimates for the error in the shift‐and‐invert approximation of the core‐functions arising in exponential integrators. The effectiveness of these error bounds is tested on several examples of interest. They can be adopted as a convenient stopping criterion for implementing the exponential Runge–Kutta algorithm in order to perform time integration. Copyright © 2013 John Wiley & Sons, Ltd.     

A direct method for solving block‐Toeplitz with near‐circulant‐block systems with applications to hybrid manufacturing systems

In this paper, we present a direct method for solving linear systems of a block‐Toeplitz matrix with each block being a near‐circulant matrix. The direct method is based on the fast Fourier transform (FFT) and the Sherman–Morrison–Woodbury formula. We give a cost analysis for the proposed method. The method is then applied to solve the steady‐state probability distribution of a hybrid manufacturing system which consists of a manufacturing process and a re‐manufacturing process. Copyright © 2005 John Wiley & Sons, Ltd.     

Approximate inversion method for time‐fractional subdiffusion equations

The finite‐difference method applied to the time‐fractional subdiffusion equation usually leads to a large‐scale linear system with a block lower triangular Toeplitz coefficient matrix. The approximate inversion method is employed to solve this system. A sufficient condition is proved to guarantee the high accuracy of the approximate inversion method for solving the block lower triangular Toeplitz systems, which are easy to verify in practice and have a wide range of applications. The applications of this sufficient condition to several existing finite‐difference schemes are investigated. Numerical experiments are presented to verify the validity of theoretical results.     

Memory‐efficient Arnoldi algorithms for linearizations of matrix polynomials in Chebyshev basis

Novel memory‐efficient Arnoldi algorithms for solving matrix polynomial eigenvalue problems are presented. More specifically, we consider the case of matrix polynomials expressed in the Chebyshev basis, which is often numerically more appropriate than the standard monomial basis for a larger degree d. The standard way of solving polynomial eigenvalue problems proceeds by linearization, which increases the problem size by a factor d. Consequently, the memory requirements of Krylov subspace methods applied to the linearization grow by this factor. In this paper, we develop two variants of the Arnoldi method that build the Krylov subspace basis implicitly, in a way that only vectors of length equal to the size of the original problem need to be stored. The proposed variants are generalizations of the so‐called quadratic Arnoldi method and two‐level orthogonal Arnoldi procedure methods, which have been developed for the monomial case. We also show how the typical ingredients of a full implementation of the Arnoldi method, including shift‐and‐invert and restarting, can be incorporated. Numerical experiments are presented for matrix polynomials up to degree 30 arising from the interpolation of nonlinear eigenvalue problems, which stem from boundary element discretizations of PDE eigenvalue problems. Copyright © 2013 John Wiley & Sons, Ltd.     

The restarted shift‐and‐invert Krylov method for matrix functions

In this paper, the numerical evaluation of matrix functions expressed in partial fraction form is addressed. The shift‐and‐invert Krylov method is analyzed, with special attention to error estimates. Such estimates give insights into the selection of the shift parameter and lead to a simple and effective restart procedure. Applications to the class of Mittag–Leffler functions are presented. Copyright © 2012 John Wiley & Sons, Ltd.     

Estimation of uTƒ(A)v for large‐scale unsymmetric matrices

Fast algorithms, based on the unsymmetric look‐ahead Lanczos and the Arnoldi process, are developed for the estimation of the functional Φ(?)= u ^T?(A) v for fixed u , v and A, where A∈??^n×n is a large‐scale unsymmetric matrix. Numerical results are presented which validate the comparable accuracy of both approaches. Although the Arnoldi process reaches convergence more quickly in some cases, it has greater memory requirements, and may not be suitable for especially large applications. Copyright © 2003 John Wiley & Sons, Ltd.     

A fast algorithm for computing the smallest eigenvalue of a symmetric positive‐definite Toeplitz matrix

Recent progress in signal processing and estimation has generated considerable interest in the problem of computing the smallest eigenvalue of a symmetric positive‐definite (SPD) Toeplitz matrix. An algorithm for computing upper and lower bounds to the smallest eigenvalue of a SPD Toeplitz matrix has been recently derived (Linear Algebra Appl. 2007; DOI: 10.1016/j.laa.2007.05.008 ). The algorithm relies on the computation of the R factor of the QR factorization of the Toeplitz matrix and the inverse of R. The simultaneous computation of R and R^?1 is efficiently accomplished by the generalized Schur algorithm. In this paper, exploiting the properties of the latter algorithm, a numerical method to compute the smallest eigenvalue and the corresponding eigenvector of SPD Toeplitz matrices in an accurate way is proposed. Copyright © 2008 John Wiley & Sons, Ltd.     

A fast second‐order difference scheme for the space–time fractional equation

In this paper, a fast second‐order accurate difference scheme is proposed for solving the space–time fractional equation. The temporal Caputo derivative is approximated by ?L2 ‐1_σ formula which employs the sum‐of‐exponential approximation to the kernel function appeared in Caputo derivative. The second‐order linear spline approximation is applied to the spatial Riemann–Liouville derivative. At each time step, a fast algorithm, the preconditioned conjugate gradient normal residual method with a circulant preconditioner (PCGNR), is used to solve the resulting system that reduces the storage and computational cost significantly. The unique solvability and unconditional convergence of the difference scheme are shown by the discrete energy method. Numerical examples are given to verify numerical accuracy and efficiency of the difference schemes.     

Generalized Bernstein‐Kantorovich–type operators on a triangle

In this note, we construct generalized Bernstein‐Kantorovich–type operators on a triangle. The concern of this note is to present a Voronovskaja‐type and Grüss Voronovskaja‐type asymptotic theorems, and some estimates of the rate of approximation with the help of K‐functional, first and second order modulus of continuity. We also obtain Korovkin‐ and Voronovskaja‐type statistical approximation theorems via weighted mean matrix method. Lastly, we show that the numerical results which explain the validity of the theoretical results and the effectiveness of the constructed operators.     

Quasi‐Toeplitz splitting iteration methods for unsteady space‐fractional diffusion equations

We construct a class of quasi‐Toeplitz splitting iteration methods to solve the two‐sided unsteady space‐fractional diffusion equations with variable coefficients. By making full use of the structural characteristics of the coefficient matrix, the method only requires computational costs of O(n log n) with n denoting the number of degrees of freedom. We develop an appropriate circulant matrix to replace the Toeplitz matrix as a preconditioner. We discuss the spectral properties of the quasi‐circulant splitting preconditioned matrix. Numerical comparisons with existing approaches show that the present method is both effective and efficient when being used as matrix splitting preconditioners for Krylov subspace iteration methods.     

Singly diagonally implicit runge‐kutta method for time‐dependent reaction‐diffusion equation

In this article, an efficient fourth‐order accurate numerical method based on Padé approximation in space and singly diagonally implicit Runge‐Kutta method in time is proposed to solve the time‐dependent one‐dimensional reaction‐diffusion equation. In this scheme, we first approximate the spatial derivative using the second‐order central finite difference then improve it to fourth‐order by applying Padé approximation. A three stage fourth‐order singly diagonally implicit Runge‐Kutta method is then used to solve the resulting system of ordinary differential equations. It is also shown that the scheme is unconditionally stable, and is suitable for stiff problems. Several numerical examples are solved by the scheme and the efficiency and accuracy of the new scheme are compared with two widely used high‐order compact finite difference methods. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 27: 1423–1441, 2011     

Analysis of a novel preconditioner for a class of p‐level lower rank extracted systems

This paper proposes and studies the performance of a preconditioner suitable for solving a class of symmetric positive definite systems, Âx=b, which we call p‐level lower rank extracted systems (p‐level LRES), by the preconditioned conjugate gradient method. The study of these systems is motivated by the numerical approximation of integral equations with convolution kernels defined on arbitrary p‐dimensional domains. This is in contrast to p‐level Toeplitz systems which only apply to rectangular domains. The coefficient matrix, Â, is a principal submatrix of a p‐level Toeplitz matrix, A, and the preconditioner for the preconditioned conjugate gradient algorithm is provided in terms of the inverse of a p‐level circulant matrix constructed from the elements of A. The preconditioner is shown to yield clustering in the spectrum of the preconditioned matrix which leads to a substantial reduction in the computational cost of solving LRE systems. Copyright © 2006 John Wiley & Sons, Ltd.     

On order‐reducible sinc discretizations and block‐diagonal preconditioning methods for linear third‐order ordinary differential equations

By introducing a variable substitution, we transform the two‐point boundary value problem of a third‐order ordinary differential equation into a system of two second‐order ordinary differential equations (ODEs). We discretize this order‐reduced system of ODEs by both sinc‐collocation and sinc‐Galerkin methods, and average these two discretized linear systems to obtain the target system of linear equations. We prove that the discrete solution resulting from the linear system converges exponentially to the true solution of the order‐reduced system of ODEs. The coefficient matrix of the linear system is of block two‐by‐two structure, and each of its blocks is a combination of Toeplitz and diagonal matrices. Because of its algebraic properties and matrix structures, the linear system can be effectively solved by Krylov subspace iteration methods such as GMRES preconditioned by block‐diagonal matrices. We demonstrate that the eigenvalues of certain approximation to the preconditioned matrix are uniformly bounded within a rectangle on the complex plane independent of the size of the discretized linear system, and we use numerical examples to illustrate the feasibility and effectiveness of this new approach. Copyright © 2013 John Wiley & Sons, Ltd.     

Structured FISTA for image restoration

In this paper, we propose an efficient numerical scheme for solving some large‐scale ill‐posed linear inverse problems arising from image restoration. In order to accelerate the computation, two different hidden structures are exploited. First, the coefficient matrix is approximated as the sum of a small number of Kronecker products. This procedure not only introduces one more level of parallelism into the computation but also enables the usage of computationally intensive matrix–matrix multiplications in the subsequent optimization procedure. We then derive the corresponding Tikhonov regularized minimization model and extend the fast iterative shrinkage‐thresholding algorithm (FISTA) to solve the resulting optimization problem. Because the matrices appearing in the Kronecker product approximation are all structured matrices (Toeplitz, Hankel, etc.), we can further exploit their fast matrix–vector multiplication algorithms at each iteration. The proposed algorithm is thus called structured FISTA (sFISTA). In particular, we show that the approximation error introduced by sFISTA is well under control and sFISTA can reach the same image restoration accuracy level as FISTA. Finally, both the theoretical complexity analysis and some numerical results are provided to demonstrate the efficiency of sFISTA.     

Approximate solutions to large nonsymmetric differential Riccati problems with applications to transport theory

In this paper, we consider large‐scale nonsymmetric differential matrix Riccati equations with low‐rank right‐hand sides. These matrix equations appear in many applications such as control theory, transport theory, applied probability, and others. We show how to apply Krylov‐type methods such as the extended block Arnoldi algorithm to get low‐rank approximate solutions. The initial problem is projected onto small subspaces to get low dimensional nonsymmetric differential equations that are solved using the exponential approximation or via other integration schemes such as backward differentiation formula (BDF) or Rosenbrock method. We also show how these techniques can be easily used to solve some problems from the well‐known transport equation. Some numerical examples are given to illustrate the application of the proposed methods to large‐scale problems.     

A note on the complex semi‐definite matrix Procrustes problem

This note outlines an algorithm for solving the complex ‘matrix Procrustes problem’. This is a least‐squares approximation over the cone of positive semi‐definite Hermitian matrices, which has a number of applications in the areas of Optimization, Signal Processing and Control. The work generalizes the method of Allwright (SIAM J. Control Optim. 1988; 26 (3):537–556), who obtained a numerical solution to the real‐valued version of the problem. It is shown that, subject to an appropriate rank assumption, the complex problem can be formulated in a real setting using a matrix‐dilation technique, for which the method of Allwright is applicable. However, this transformation results in an over‐parametrization of the problem and, therefore, convergence to the optimal solution is slow. Here, an alternative algorithm is developed for solving the complex problem, which exploits fully the special structure of the dilated matrix. The advantages of the modified algorithm are demonstrated via a numerical example. Copyright © 2007 John Wiley & Sons, Ltd.     

Solving 2D time‐fractional diffusion equations by a pseudospectral method and Mittag‐Leffler function evaluation

Two‐dimensional time‐fractional diffusion equations with given initial condition and homogeneous Dirichlet boundary conditions in a bounded domain are considered. A semidiscrete approximation scheme based on the pseudospectral method to the time‐fractional diffusion equation leads to a system of ordinary fractional differential equations. To preserve the high accuracy of the spectral approximation, an approach based on the evaluation of the Mittag‐Leffler function on matrix arguments is used for the integration along the time variable. Some examples along with numerical experiments illustrate the effectiveness of the proposed approach. Copyright © 2016 John Wiley & Sons, Ltd.     

Directional ‐matrix compression for high‐frequency problems

Standard numerical algorithms, such as the fast multipole method or ‐matrix schemes, rely on low‐rank approximations of the underlying kernel function. For high‐frequency problems, the ranks grow rapidly as the mesh is refined, and standard techniques are no longer attractive. Directional compression techniques solve this problem by using decompositions based on plane waves. Taking advantage of hierarchical relations between these waves' directions, an efficient approximation is obtained. This paper is dedicated to directional ‐matrices that employ local low‐rank approximations to handle directional representations efficiently. The key result is an algorithm that takes an arbitrary matrix and finds a quasi‐optimal approximation of this matrix as a directional ‐matrix using a prescribed block tree. The algorithm can reach any given accuracy, and the approximation requires only units of storage, where n is the matrix dimension, κ is the wave number, and k is the local rank. In particular, we have a complexity of if κ is constant and for high‐frequency problems characterized by κ²～n. Because the algorithm can be applied to arbitrary matrices, it can serve as the foundation of fast techniques for constructing preconditioners.     

IRAM‐based method for eigenpairs and their derivatives of large matrix‐valued functions

Based on the implicitly restarted Arnoldi method for eigenpairs of large matrix, a new method is presented for the computation of a few eigenpairs and their derivatives of large matrix‐valued functions. Eigenpairs and their derivatives are calculated simultaneously. Equation systems that are solved for eigenvector derivatives are greatly reduced from the original matrix size. The left eigenvectors are not required. Hence, the computational cost is saved. The convergence theory of the proposed method is established. Finally, numerical experiments are given to illustrate the efficiency of the proposed method. Copyright © 2010 John Wiley & Sons, Ltd.