Computing Linear Combinations of φ \varphi -Function Actions for Exponential Integrators

Awad H. Al-Mohy · 2025

Read Computing Linear Combinations of φ \varphi -Function Actions for Exponential Integrators by Awad H. Al-Mohy (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-26475.txt.

Introduction

Awad Al-Mohy speeds up a family of matrix functions that exponential integrators lean on, in a 2025 paper. These phi-functions blend a matrix with vectors in stacked combinations. His algorithm never builds the matrix functions directly. It pairs a scaling-and-recovery trick with a cut-off Taylor series, choosing the shift and scale to minimize a power-based cost.

Accuracy is dialed by the user and capped only by machine precision. A block version evaluates many combinations at once, and the stage times stay decoupled from the weights. On stiff and badly nonnormal test matrices, the method held near-machine accuracy at small steps and stayed reliable at large steps where rival Krylov methods faded. The authors claim a better balance of trust and cost.

Catalog record

CREATORAwad H. Al-Mohy
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-26475

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computing Linear Combinations of φ \varphi -Function Actions for Exponential Integrators Awad H. Al-Mohy Abstract We propose a matrix-free algorithm for evaluating linear combinations of φ \varphi -function actions, w i := ∑ j = 0 p α i j ​ φ j ​ ( t i ​ A ) ​ v j w_{i}:=\sum_{j=0}^{p}\alpha_{i}^{\,j}\,\varphi_{j}(t_{i}A)v_{j} for i = 1 : r i=1\colon r , arising in exponential integrators. The method combines the scaling and recovering method with a truncated Taylor series, choosing a spectral shift and a scaling parameter by minimizing a power-based objective of the shifted operator. Accuracy is user-controlled and ultimately limited by the working precision. The algorithm decouples the stage abscissae t i t_{i} from the polynomial weights α i j \alpha_{i}^{j} , and a block variant enables simultaneous evaluation of { w i } i = 1 r \{w_{i}\}_{i=1}^{r} . Across standard benchmarks, including stiff and highly nonnormal matrices, the algorithm attains near-machine accuracy (IEEE double precision in our tests) for small step sizes and maintains reliable accuracy for larger steps where several existing Krylov-based algorithms deteriorate, providing a favorable balance of reliability and computational cost. Keywords. Exponential integrators; \varphi -functions; matrix exponential; matrix-free algorithms. 1 Introduction The evaluation of the action of the matrix exponential and its related functions plays a significant role in the exponential time integration methods for semilinear problem of the form u^{\prime}(t)=f(t,u(t))=A\,u(t)+g(t,u(t)),\quad u(t_{0})=u_{0}, (1.1) where u(t)\in\mathbb{C}^{n} , A\in\mathbb{C}^{n\times n} is a matrix representing spatial discitization of a partial differential equation, and g is a nonlinear vector function. Exponential integrator schemes for the problem ( 1.1 ) involve linear combinations of the form [ 3 , 8 , 11 , 10 , 12 , 17 ] w_{i}:=\sum_{j=0}^{p}\alpha_{i}^{\,j}\,\varphi_{j}(t_{i}A)v_{j},\quad i=1\colon r, (1.2) where t_{i} are stage abscissae, \alpha_{i}^{j} are polynomial weights, and \varphi_{0}(tA)=\mathrm{e}^{tA},\quad\varphi_{j}(tA)=\sum_{k=0}^{\infty}\frac{t^{k}A^{k}}{(k+j)!},\quad j\in\mathbb{N}^{+}, (1.3) For instance, the fourth-order six-stage exponential Runge–Kutta integrator ( expRK4s6 ) proposed by Luan [ 13 ] takes the form: \displaystyle U_{n2} \displaystyle=u_{n}+\varphi_{1}(c_{2}hA)\,c_{2}h\,f(t_{n},u_{n}), (1.4) \displaystyle U_{n,k} \displaystyle=u_{n}+\varphi_{1}(c_{k}hA)\,c_{k}h\,f(t_{n},u_{n})+\varphi_{2}(c_{k}hA)\,\frac{c_{k}^{2}}{c_{2}}\,h\,D_{n2}, \displaystyle k=3,4, \displaystyle U_{n,j} \displaystyle=u_{n}+\varphi_{1}(c_{j}hA)\,c_{j}h\,f(t_{n},u_{n})+\varphi_{2}(c_{j}hA)\,\frac{c_{j}^{2}}{\,c_{3}-c_{4}\,}\,h\!\left(-\frac{c_{4}}{c_{3}}D_{n3}+\frac{c_{3}}{c_{4}}D_{n4}\right) \displaystyle+\varphi_{3}(c_{j}hA)\,\frac{2c_{j}^{3}}{\,c_{3}-c_{4}\,}\,h\!\left(\frac{1}{c_{3}}D_{n3}-\frac{1}{c_{4}}D_{n4}\right), \displaystyle j=5,6, \displaystyle u_{n+1} \displaystyle=u_{n}+\varphi_{1}(hA)\,h\,f(t_{n},u_{n})+\varphi_{2}(hA)\,\frac{1}{\,c_{5}-c_{6}\,}\,h\!\left(-\frac{c_{6}}{c_{5}}D_{n5}+\frac{c_{5}}{c_{6}}D_{n6}\right) \displaystyle+\varphi_{3}(hA)\,\frac{2}{\,c_{5}-c_{6}\,}\,h\!\left(\frac{1}{c_{5}}D_{n5}-\frac{1}{c_{6}}D_{n6}\right), where h is the time step size, D_{ni}:=g(t_{n}+c_{i}h,U_{ni})-g(t_{n},u_{n}) for 2\leq i\leq 6 , and c_{2}=c_{3}=1/2 , c_{4}=c_{6}=1/3 , c_{5}=5/6 . Given an algorithm for evaluating such linear combinations, scheme ( 1.4 ) requires six invocations per step (e.g., the algorithm of Niesen and Wright [ 17 ] ). However, the stages \{U_{n3},U_{n4}\} , on the one hand, and \{U_{n5},U_{n6}\} , on the other, are independent—so each pair can be computed simultaneously (in parallel) once the required increments D_{n2} and \{D_{n3},D_{n4}\} are available. Luan et al. [ 14 ] , Gaudreault et al. [ 8 ] , and Caliari et al. [ 5 ] propose algorithms that reduce the number of calls per step to four by evaluating the independent stage pairs simultaneously. The main scope of this manuscript is to develop an algorithm that computes the linear combinations ( 1.2 ) simultaneously. Our work is organized as follows. Section 2 derives the method, building on Al-Mohy’s analysis [ 1 ] , where an operator \mathcal{D}_{f} acting on a matrix function f is defined and its properties are analyzed; this operator underpins our analysis and derivation. Section 3 presents a Taylor series error analysis and our strategy for selecting the algorithmic parameters: we specify how to compute the scaling parameter and an optimal spectral shift, and we introduce a truncation criterion for the Taylor series. Section 4 describes two versions of the algorithm. Section 5 reports extensive numerical experiments. Finally, Section 6 offers concluding remarks. 2 Method derivation In this section we present the theoretical framework of our algorithm for computing the linear combinations ( 1.2 ). We begin with the following theorem. Theorem 1 . Let A\in\mathbb{C}^{n\times n} , V=\begin{bmatrix}v_{0}&v_{p}&v_{p-1}&\cdots&v_{1}\end{bmatrix}\in\mathbb{C}^{n\times(p+1)} , J=[0]\oplus J_{p}(0) , where J_{p}(0)\in\mathbb{C}^{p\times p} is the Jordan block associated with zero, and S=\sum_{k=1}^{\infty}\frac{D_{k}}{k!},\quad D_{k}=(A/s)D_{k-1}+D_{1}(J/s)^{k-1},\quad D_{1}=V/s,\quad s\in\mathbb{N}^{+}. (2.1) Then the recurrence F_{k+1}=\mathrm{e}^{A/s}F_{k}+S\mathrm{e}^{kJ/s},\quad F_{1}=S,\quad k=1\colon s-1 (2.2) yields F_{s}=\begin{bmatrix}\varphi_{1}(A)v_{0}&\varphi_{1}(A)v_{p}&\varphi_{1}(A)v_{p-1}+\varphi_{2}(A)v_{p}&\cdots&\sum_{k=1}^{p}\varphi_{k}(A)v_{k}\end{bmatrix}, (2.3) where the j th column of F_{s} is F_{s}(:,j)=\sum_{k=1}^{j-1}\varphi_{k}(A)v_{p-j+k+1} , 2\leq j\leq p+1 . Consequently, we have \mathrm{e}^{A}v_{0}=AF_{s}(:,1)+v_{0} . Proof. We have e^{z}=\left(\mathrm{e}^{z/s}\right)^{s} for any z\in\mathbb{C} and any natural number s . Applying the linear operator \mathcal{D} defined in [ 1 , Def. 1.1] at the ordered pair (A,J) in direction V using the chain rule [ 1 , Lem. 1.2 (6)] , we obtain \mathcal{D}_{\exp}(A,J,V)=\mathcal{D}_{z^{s}}\left(\mathrm{e}^{A/s},\mathrm{e}^{J/s},S\right), (2.4) where S=\mathcal{D}_{\exp}(A/s,J/s,V/s) . We have \mathrm{e}^{z}=\sum_{k=0}^{\infty}z^{k}/k! . Thus, S=\sum_{k=1}^{\infty}\mathcal{D}_{z^{k}}\left(A/s,J/s,V/s\right)/k!. Since z^{k}=z\cdot z^{k-1} , we have D_{k}:=\mathcal{D}_{z^{k}}\left(A/s,J/s,V/s\right)=\left(\frac{A}{s}\right)\mathcal{D}_{z^{k-1}}+\left(\frac{V}{s}\right)\left(\frac{J}{s}\right)^{k-1}, obtained from the product rule of the operator \mathcal{D} . Thus, the product rule applied again to the right hand side of ( 2.4 ) yields \mathcal{D}_{\exp}(A,J,V)=\mathrm{e}^{A/s}\mathcal{D}_{z^{s-1}}+S\left(\mathrm{e}^{J/s}\right)^{s-1}=:F_{s} It remains to clarify the relation ( 2.3 ). By [ 1 , Eq. (1.2)] , \mathcal{D}_{\exp}(A,J,V) is the (1,2) block of \exp\left(\begin{bmatrix}A&V\\ 0&J\end{bmatrix}\right) . Reblocking the matrix as \begin{bmatrix}A&V\\ 0&J\end{bmatrix}=\begin{bmatrix}\begin{bmatrix}A&v_{0}\\ 0&0\end{bmatrix}&\begin{matrix}v_{p}&v_{p-1}&\cdots&v_{1}\\ 0&0&\cdots&0\end{matrix}\\ 0&J_{p}(0)\end{bmatrix}, taking the exponential of both sides, and applying [ 3 , Thm. 2.1] on the right hand side for the matrix \begin{bmatrix}A&v_{0}\\ 0&0\end{bmatrix} and the vectors \begin{bmatrix}v_{j}\\ 0\end{bmatrix} , j=1\colon p using the relation \varphi_{\ell}\left(\begin{bmatrix}A&v_{0}\\ 0&0\end{bmatrix}\right)=\begin{bmatrix}\varphi_{\ell}(A)&\varphi_{\ell+1}(A)v_{0}\\ 0&\frac{1}{\ell!}\end{bmatrix}, the result follows immediately. ∎ This theorem leads to the following important corollary. Corollary 2 . Under the assumptions of Theorem 1 with the matrix J replaced by \alpha\,J for some nonzero \alpha\in\mathbb{C} , the first and last columns of the resulting matrix F_{s}^{(\alpha)} are F_{s}^{(\alpha)}(:,1)=\varphi_{1}(A)v_{0},\quad F_{s}^{(\alpha)}(:,p+1)=\varphi_{1}(A)v_{1}+\alpha\varphi_{2}(A)v_{2}+\alpha^{2}\varphi_{3}(A)v_{3}+\cdots+\alpha^{p-1}\varphi_{p}(A)v_{p}. Proof. Consider the diagonal matrix \Delta=\mathrm{diag}(1,\,\alpha,\,\alpha^{2},\cdots,\,\alpha^{p}) . We have \alpha\,J=\Delta^{-1}J\Delta . By Al-Mohy [ 1 , Lem. 1.2 (2)] , we have \mathcal{D}_{\exp}(A,\alpha\,J,V)=\mathcal{D}_{\exp}(A,J,V\Delta^{-1})\Delta. Applying Theorem 1 for A , J , and V\Delta^{-1}=\begin{bmatrix}v_{0}&\alpha^{-1}v_{p}&\alpha^{-2}v_{p-1}&\cdots&\alpha^{-p}v_{1}\end{bmatrix} yields \mathcal{D}_{\exp}(A,J,V\Delta^{-1})=\begin{bmatrix}\varphi_{1}(A)v_{0}&\alpha^{-1}\varphi_{1}(A)v_{p}&\cdots&\sum_{k=1}^{p}\alpha^{k-p-1}\varphi_{k}(A)v_{k}\end{bmatrix}. The result follows by multiplying through from the right by \Delta and extracting the first and the last columns. ∎ 3 Error analysis and parameter selection Theorem 1 forms the basis for our algorithm. We use a truncated Taylor series, T_{m}(z)=\sum_{k=0}^{m}z^{k}/k! , to approximate the exponential function \mathrm{e}^{z} . As Taylor polynomial yields good approximation near the origin, we need to take the scaling parameter s large enough to accelerate the convergence. The matrix S in ( 2.1 ) is computed once then passed to the recurrence ( 2.2 ) to recover the effect of the scaling. We then extract the first and last columns of the matrix F_{s} to evaluate the linear combination ( 1.2 ). If s is large, the computation is dominate by the s-1 actions of the matrix exponential \mathrm{e}^{A/s} on F_{k} in ( 2.2 ). Therefore, it is important to keep s as small as possible. Al-Mohy and Higham [ 3 ] propose shifting the diagonal entries of the matrix A by \mathrm{trace}(A)/n , scaling the shifted matrix, premature termination of Taylor polynomial if a relative forward error achieves a given tolerance. Since the matrix A is accessible via matrix-vector product only, the evaluation of \mathrm{trace}(A) is not straightforward. Therefore we develop a new approach to shift A . We have \left\|\mathrm{e}^{A/s}v-T_{m-1}(A/s)v\right\|\leq\frac{\|A^{m}v\|}{s^{m}m!}+\left\|\sum_{k=m+1}^{\infty}\frac{A^{k}v}{s^{k}k!}\right\|, (3.1) where v is a unit vector. Now, consider the scalar function \nu(\xi)=\|(A-\xi I)^{m}u\|=\left\|\sum_{k=0}^{m}\binom{m}{k}\xi^{m-k}w_{k}\right\|, (3.2) where w_{k+1}=Aw_{k} with w_{0}=v . Suppose \xi^{*} is a minimizer of \nu(\xi) . Thus, for a given tolerance, \mathrm{tol} , we choose s such that s^{-m}\nu(\xi^{*})/m!\leq\mathrm{tol} . We use the spectral norm for its smoothness. Algorithm 1 Selection of scaling and shift parameters ( s , \xi^{\ast} ) 1: Input: Matrix A\in\mathbb{C}^{n\times n} or linear

Read the complete text