Piecewise interpolants on matrix lie groups

Here we consider a numerical procedure to interpolate on matrix Lie groups. By using the exponential map and its (1, 1) diagonal Padé approximant, piecewice interpolants may be derived. The approach based on the Padé map has the advantage that the computation of exponentials and logarithms of matrices are reduced. We show that the updating technique proposed by Enright in [1] may be applied when a dense output is required. The application to the numerical solution of a system ODEs on matrix group and to a classical interpolation problem are reported.     

Computing multiple integrals involving matrix exponentials

In this paper, a generalization of a formula proposed by Van Loan [Computing integrals involving the matrix exponential, IEEE Trans. Automat. Control 23 (1978) 395–404] for the computation of multiple integrals of exponential matrices is introduced. In this way, the numerical evaluation of such integrals is reduced to the use of a conventional algorithm to compute matrix exponentials. The formula is applied for evaluating some kinds of integrals that frequently emerge in a number classical mathematical subjects in the framework of differential equations, numerical methods and control engineering applications.     

The scaling and modified squaring method for matrix functions related to the exponential

In recent years, there has been a resurgence in the construction and implementation of exponential integrators, which are numerical methods specifically designed for the numerical solution of spatially discretized semi-linear partial differential equations. Exponential integrators use the matrix exponential and related matrix functions within the formulation of the numerical method. The scaling and squaring method is the most widely used method for computing the matrix exponential. The aim of this paper is to discuss the efficient and accurate evaluation of the matrix exponential and related matrix functions using a scaling and modified squaring method.     

Implementation of exponential Rosenbrock-type integrators

In this paper, we present a variable step size implementation of exponential Rosenbrock-type methods of orders 2, 3 and 4. These integrators require the evaluation of exponential and related functions of the Jacobian matrix. To this aim, the Real Leja Points Method is used. It is shown that the properties of this method combine well with the particular requirements of Rosenbrock-type integrators. We verify our implementation with some numerical experiments in MATLAB, where we solve semilinear parabolic PDEs in one and two space dimensions. We further present some numerical experiments in FORTRAN, where we compare our method with other methods from literature. We find a great potential of our method for non-normal matrices. Such matrices typically arise in parabolic problems with large advection in combination with moderate diffusion and mildly stiff reactions.     

Symmetric spaces and Lie triple systems in numerical analysis of differential equations

A remarkable number of different numerical algorithms can be understood and analyzed using the concepts of symmetric spaces and Lie triple systems, which are well known in differential geometry from the study of spaces of constant curvature and their tangents. This theory can be used to unify a range of different topics, such as polar-type matrix decompositions, splitting methods for computation of the matrix exponential, composition of selfadjoint numerical integrators and dynamical systems with symmetries and reversing symmetries. The thread of this paper is the following: involutive automorphisms on groups induce a factorization at a group level, and a splitting at the algebra level. In this paper we will give an introduction to the mathematical theory behind these constructions, and review recent results. Furthermore, we present a new Yoshida-like technique, for self-adjoint numerical schemes, that allows to increase the order of preservation of symmetries by two units. The proposed techniques has the property that all the time-steps are positive.     

Comparison of software for computing the action of the matrix exponential

The implementation of exponential integrators requires the action of the matrix exponential and related functions of a possibly large matrix. There are various methods in the literature for carrying out this task. In this paper we describe a new implementation of a method based on interpolation at Leja points. We numerically compare this method with other codes from the literature. As we are interested in applications to exponential integrators we choose the test examples from spatial discretization of time dependent partial differential equations in two and three space dimensions. The test matrices thus have large eigenvalues and can be nonnormal.     

Approximation of the linear combination of $\varphi$-functions using the block shift-and-invert Krylov subspace method

In this paper, we develop an algorithm in which the block shift-and-invert Krylov subspace method can be employed for approximating the linear combination of the matrix exponential and related exponential-type functions. Such evaluation plays a major role in a class of numerical methods known as exponential integrators. We derive a low-dimensional matrix exponential to approximate the objective function based on the block shift-and-invert Krylov subspace methods. We obtain the error expansion of the approximation, and show that the variants of its first term can be used as reliable a posteriori error estimates and correctors. Numerical experiments illustrate that the error estimates are efficient and the proposed algorithm is worthy of further study.     

Exponential Rosenbrock integrators for option pricing

In this paper, we are concerned with the time integration of differential equations modeling option pricing. In particular, we consider the Black-Scholes equation for American options. As an alternative to existing methods, we present exponential Rosenbrock integrators. These integrators require the evaluation of the exponential and related functions of the Jacobian matrix. The resulting methods have good stability properties. They are fully explicit and do not require the numerical solution of linear systems, in contrast to standard integrators. We have implemented some numerical experiments in Matlab showing the reliability of the new method.     

The Cayley Method and the Inverse Eigenvalue Problem for Toeplitz Matrices

Despite the fact that symmetric Toeplitz matrices can have arbitrary eigenvalues, the numerical construction of such a matrix having prescribed eigenvalues remains to be a challenge. A two-step method using the continuation idea is proposed in this paper. The first step constructs a centro-symmetric Jacobi matrix with the prescribed eigenvalues in finitely many steps. The second step uses the Cayley transform to integrate flows in the linear subspace of skew-symmetric and centro-symmetric matrices. No special geometric integrators are needed. The convergence analysis is illustrated for the case of n = 3. Numerical examples are presented.     

二项指数和四次混合均值的计算

本文研究了二项指数和四次均值的计算问题.利用初等数论及代数数论的方法获得了一个精确的计算公式以及一个转换公式,推广了已有的结果,揭示了均值计算与同余方程组的本质联系.     

A quadrature based method for evaluating exponential-type functions for exponential methods

We present a quadrature-based method to evaluate exponential-like operators required by different kinds of exponential integrators. The method approximates these operators by means of a quadrature formula that converges like O(e ^−cK ), with K the number of quadrature nodes, and it is useful when solving parabolic equations. The approach allows also the evaluation of the associated scalar mappings. The method is based on numerical inversion of sectorial Laplace transforms. Several numerical illustrations are provided to test the algorithm, including examples with a mass matrix and the application of the method inside the MATLAB package EXP4, an adaptive solver based on an exponential Runge–Kutta method.     

Automatic differentiation of numerical integration algorithms

Automatic differentiation (AD) is a technique for automatically augmenting computer programs with statements for the computation of derivatives. This article discusses the application of automatic differentiation to numerical integration algorithms for ordinary differential equations (ODEs), in particular, the ramifications of the fact that AD is applied not only to the solution of such an algorithm, but to the solution procedure itself. This subtle issue can lead to surprising results when AD tools are applied to variable-stepsize, variable-order ODE integrators. The computation of the final time step plays a special role in determining the computed derivatives. We investigate these issues using various integrators and suggest constructive approaches for obtaining the desired derivatives.

     

Comparison of methods for evaluating functions of a matrix exponential

We compare six different categories of numerical methods for the evaluation of functions of the matrix exponential. These functions are required for exponential integrators, and are not straightforward to evaluate because they are highly susceptible to rounding errors when the matrix has small eigenvalues. The comparison takes into account both accuracy and computational time. A scaling and squaring algorithm and a diagonalisation algorithm are both found to be efficient.     

Convergence of rational multistep methods of Adams-Padé type

Rational generalizations of multistep schemes, where the linear stiff part of a given problem is treated by an A-stable rational approximation, have been proposed by several authors, but a reasonable convergence analysis for stiff problems has not been provided so far. In this paper we directly relate this approach to exponential multistep methods, a subclass of the increasingly popular class of exponential integrators. This natural, but new interpretation of rational multistep methods enables us to prove a convergence result of the same quality as for the exponential version. In particular, we consider schemes of rational Adams type based on A-acceptable Padé approximations to the matrix exponential. A numerical example is also provided.     

A method for approximation of the exponential map in semidirect product of matrix Lie groups and some applications

In this paper we explore the computation of the matrix exponential in a manner that is consistent with Lie group structure. Our point of departure is the decomposition of Lie algebra as the semidirect product of two Lie subspaces and an application of the Baker-Campbell-Hausdorff formula. Our results extend the results in Iserles and Zanna (2005) [2], Zanna and Munthe-Kaas(2001/02) [4] to a range of Lie groups: the Lie group of all solid motions in Euclidean space, the Lorentz Lie group of all solid motions in Minkowski space and the group of all invertible (upper) triangular matrices. In our method, the matrix exponential group can be computed by a less computational cost and is more accurate than the current methods. In addition, by this method the approximated matrix exponential belongs to the corresponding Lie group.     

Using the RD rational Arnoldi method inside exponential integrators

We consider the use of the Restricted-Denominator (RD) rational Arnoldi method for the computation of the core functions of exponential integrators for parabolic problems. Reliable and easy-to-use a-posteriori error bounds are presented. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Magnus integrators for solving linear-quadratic differential games

We consider Magnus integrators to solve linear-quadratic N$N$-player differential games. These problems require to solve, backward in time, non-autonomous matrix Riccati differential equations which are coupled with the linear differential equations for the dynamic state of the game, to be integrated forward in time. We analyze different Magnus integrators which can provide either analytical or numerical approximations to the equations. They can be considered as time-averaging methods and frequently are used as exponential integrators. We show that they preserve some of the most relevant qualitative properties of the solution for the matrix Riccati differential equations as well as for the remaining equations. The analytical approximations allow us to study the problem in terms of the parameters involved. Some numerical examples are also considered which show that exponential methods are, in general, superior to standard methods.     

Uniformly Accurate Multiscale Time Integrators for Highly Oscillatory Second Order Differential Equations

In this paper, two multiscale time integrators (MTIs), motivated from two types of multiscale decomposition by either frequency or frequency and amplitude, are proposed and analyzed for solving highly oscillatory second order differential equations with a dimensionless parameter $0 < \varepsilon≤ 1.$ In fact, the solution to this equation propagates waves with wavelength at $O(\varepsilon^2)$ when $0<\varepsilon≪1,$ which brings significantly numerical burdens in practical computation. We rigorously establish two independent error bounds for the two MTIs at $O(\tau^2/\varepsilon^2)$ and $O(\varepsilon^2)$ for $\varepsilon ∈ (0,1]$ with $\tau > 0$ as step size, which imply that the two MTIs converge uniformly with linear convergence rate at $O(\tau)$ for $ε ∈ (0,1]$ and optimally with quadratic convergence rate at $O(\tau^2)$ in the regimes when either $ε=O(1)$ or $0<ε≤\tau.$ Thus the meshing strategy requirement (or $ε$-scalability) of the two MTIs is $\tau =O(1)$ for $0<ε≪1,$ which is significantly improved from $\tau =O(ε^3)$ and $\tau =O(ε^2)$ requested by finite difference methods and exponential wave integrators to the equation, respectively. Extensive numerical tests and comparisons with those classical numerical integrators are reported, which gear towards better understanding on the convergence and resolution properties of the two MTIs. In addition, numerical results support the two error bounds very well.     

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.     

Generalized polar coordinates on Lie groups and numerical integrators

Motivated by developments in numerical Lie group integrators, we introduce a family of local coordinates on Lie groups denoted generalized polar coordinates. Fast algorithms are derived for the computation of the coordinate maps, their tangent maps and the inverse tangent maps. In particular we discuss algorithms for all the classical matrix Lie groups and optimal complexity integrators for n-spheres.