betaFeedback

WorksMathematics

High-order Crank-Nicolson method via diagonal Padé factorization

Abstract

We present a numerical method to solve the time-dependent Schrödinger equation at arbitrary order of accuracy in the time step, particularly well suited for tridiagonal Hamilton operators. The method is based on a factorization of the diagonal Padé approximants of the matrix exponential into products of linear factors, which preserves tridiagonal matrix structure at every time step and yields a propagator of order 2q in the time step at a cost of O(qN) operations. The propagator is exactly unitary by construction, and at lowest order q=1 it reduces to the standard Crank-Nicolson algorithm. We further extend the method to any Hamiltonian admitting a decomposition into a sum of tridiagonal or diagonal operators via high-order split-operator techniques (McLachlan, 2022), retaining O(qN) scaling at each time step. We also analytically show and numerically verify that the precision is dictated by the split-operator method. This covers a broad range of physically relevant cases, including higher-dimensional systems, higher-order spatial discretizations, and non-separable potentials.

Introduction

Since its original formulation for evaluating numerically heat conduction Crank and Nicolson, [4], the Crank-Nicolson method has become a fundamental numerical scheme for solving parabolic partial differential equations. Today, Crank-Nicolson algorithms are found in a wide array of scientific and engineering disciplines due to their unconditional stability and second-order accuracy in both time and space. Beyond classical thermodynamics, they are heavily utilized in quantitative finance to solve the Black-Scholes equation for robust option pricing Wilmott, Dewynne and Howison, [18]; Duffy [5], and in computational fluid dynamics to compute viscous diffusion flows Anderson, [2]. The method is also a standard tool for modeling complex reaction-diffusion systems in mathematical biology Murray, [13], as well as in implicit finite-difference time-domain schemes for accelerating electromagnetic simulations Taflove and Hagness, [16]. Here, we will focus on the time dependent Schrödinger equation (TDSE) as an example Tannor, [17].

Time-dependent Schrödinger equation

The TDSE arises across a wide range of applications in modern physics and physical chemistry Kulander, Schafer and Krause, [10]. It governs the time evolution of the quantum state ∣ψ(t)⟩|\psi(t)\rangle of a system described by a time-independent Hamiltonian H\mathrm{H}. Setting ℏ=1\hbar=1, its formal solution over a time interval [0,T][0,T] reads

∣ψ(T)⟩=exp⁡(−i H T)∣ψ(0)⟩,(1)|\psi(T)\rangle= \exp(-\mathrm{i}\,\mathrm{H}\,T)|\psi(0)\rangle, \tag*{(1)}

where ∣ψ(0)⟩|\psi(0)\rangle is the initial state. For clarity we restrict attention to the time-independent case throughout, although the extension to time-dependent Hamiltonians H(t)\mathrm{H}(t) is straightforward via a Magnus expansion or a piecewise-constant approximation of H(t)\mathrm{H}(t) over each time step Blanes, Casas, Oteo and Ros, [3].

Once H\mathrm{H} is represented as a matrix, evaluating (1) requires computing the action of a matrix exponential on a vector. A broad and physically important class of Hamiltonians admits a tridiagonal matrix representation, including finite-difference discretizations of the kinetic energy operator on a spatial grid, collective spin models, bosonic and fermionic tight-binding chains, and nearest-neighbour lattice models Golub and Van Loan, [6]. More generally, many systems lead to banded matrices, or to Hamiltonians that decompose naturally into a sum of tridiagonal and diagonal contributions. The present work places its primary focus on tridiagonal H\mathrm{H}, and shows how the method extends naturally to banded matrices and, via operator splitting, to the broader class of Hamiltonians admitting such a decomposition.

For long propagation times the interval [0,T][0,T] is split into NtN_t steps of size δt=T/Nt\delta t=T/N_t, and the evolution of the quantum state over one time-step interval reads as

∣ψ(t+δt)⟩=exp⁡(−i H δt)∣ψ(t)⟩,(2)|\psi(t+\delta t)\rangle= \exp(-\mathrm{i}\,\mathrm{H}\,\delta t)|\psi(t)\rangle, \tag*{(2)}

with t=n δtt=n\,\delta t for n=0,1,…,Nt−1n=0,1,\ldots,N_t-1. This partitioning strategy is closely related to the scaling and squaring approach Higham, [9], although the two settings differ fundamentally: here NtN_t is determined by the required physical time resolution rather than by numerical optimisation of a single matrix exponential computation. We denote the exact propagator over one time step by

U(δt)=exp⁡(−i δt H),(3)U(\delta t)=\exp(-\mathrm{i}\,\delta t\,\mathrm{H}), \tag*{(3)}

so that Eq. (2) reads ∣ψ(t+δt)⟩=U(δt)∣ψ(t)⟩|\psi(t+\delta t)\rangle=U(\delta t)|\psi(t)\rangle, or in vector notation

u=U(δt) v,(4)\mathbf{u}=U(\delta t)\,\mathbf{v}, \tag*{(4)}

where u=∣ψ(t+δt)⟩\mathbf{u}=|\psi(t+\delta t)\rangle and v=∣ψ(t)⟩\mathbf{v}=|\psi(t)\rangle. The goal is to compute an approximation U~(δt)\widetilde{U}(\delta t) to U(δt)U(\delta t) satisfying

∥U~(δt)−U(δt)∥=O(δtr+1),(5)\left\|\widetilde{U}(\delta t)-U(\delta t)\right\|=O(\delta t^{r+1}), \tag*{(5)}

ORCID(s): 0000-0002-2460-295X (L. Freschi); 0000-0002-7087-1798 (C. Lévêque); 0000-0001-6301-6008 (J. Caillat); 0000-0001-6301-6008 (R. Taïeb); 0000-0002-6976-5488 (J. Dubois).

where rr denotes the order of accuracy, such that U~(δt)v\widetilde{U}(\delta t)\mathbf{v} can be computed efficiently for tridiagonal H\mathbb{H}. Different approaches are employed in the literature to construct such approximations, as reviewed below.

Existing approaches

FFT split-operator methods. High-order split-operator schemes decompose the propagator into alternating kinetic and potential factors evaluated via the Fast Fourier Transform [12]. They achieve O(Nlog⁡N)O(N \log N) cost per step and preserve unitarity for chosen splitting coefficients, but require a uniform periodic grid and a separable Hamiltonian.

Krylov subspace methods. The action U(δt)vU(\delta t)\mathbf{v} can be approximated via Lanczos or Arnoldi iteration in a Krylov subspace [15]. The expmv algorithm of Al-Mohy and Higham [1] provides rigorous error control for general sparse matrices, but does not guarantee exact unitarity and may require many Krylov vectors for tight accuracy requirements.

Crank-Nicolson method. The simplest scheme with exact norm conservation is the Crank-Nicolson (CN) method [4],

(1+iδt2H)u=(1−iδt2H)v,(6)\left(1+\mathrm{i}\frac{\delta t}{2}\mathbb{H}\right)\mathbf{u}=\left(1-\mathrm{i}\frac{\delta t}{2}\mathbb{H}\right)\mathbf{v}, \tag*{(6)}

which is second-order accurate in δt\delta t and exactly unitary for Hermitian H\mathbb{H}. When H\mathbb{H} is tridiagonal, both operations cost O(N)O(N) via the Thomas algorithm. However, CN is limited to second-order accuracy and no established high-order generalization that retains O(N)O(N) tridiagonal scaling exists in the literature.

Present work

The goal of this work is to preserve the O(N)O(N) efficiency of tridiagonal matrix operations while extending temporal accuracy to arbitrary order. We achieve this through two ideas. First, we employ the diagonal [q,q][q,q] Padé approximant [14] Rq,q(z)=Pq(z)/Pq(−z)R_{q,q}(z)=P_q(z)/P_q(-z), which approximates eze^z to order 2q2q and PqP_q is real, ensuring exact unitarity. Second, we factorize Pq(z)=∏k=1q(1+αkz)P_q(z)=\prod_{k=1}^{q}(1+\alpha_k z), where αk\alpha_k are the roots of PqP_q. Each factor [1−αk(i δt H)][1-\alpha_k(\mathrm{i}\,\delta t\,\mathbb{H})] is tridiagonal whenever H\mathbb{H} is tridiagonal, reducing the full propagator to qq sequential Thomas solves and qq matrix–vector products, all O(N)O(N), for a total cost of O(qN)O(qN) per time step. At q=1q=1 with α1=1/2\alpha_1=1/2 the method recovers the standard CN scheme (6).

We further extend the method beyond the single-operator tridiagonal case by combining it with the high-order split-operator framework of [12]. Any Hamiltonian decomposable as H=∑iHi\mathbb{H}=\sum_i\mathbb{H}_i, with each Hi\mathbb{H}_i tridiagonal or diagonal, can be handled at the same O(qN)O(qN) cost per time step, covering multi-dimensional systems, higher-order spatial discretizations, and non-separable potentials alike.

The specific contributions of this paper, detailed in the sections that follow, are: § 2 introduces the diagonal Padé propagator, its factorization, and validates it on a one-dimensional benchmark § 2.4. § 3 extends the method to higher-dimensional systems via operator splitting and validates the combined algorithm on a two-dimensional system with a non-separable potential § 3.5. § 4 concludes.

The diagonal Padé propagator and its factorization

Padé approximants of exp(zz) and the Rq,qR_{q,q} family

The Padé approximant of order [p,q][p,q] of the exponential is the rational function Rp,q(z)=Pp,q(z)/Qp,q(z)R_{p,q}(z)=P_{p,q}(z)/Q_{p,q}(z), where Pp,qP_{p,q} and Qp,qQ_{p,q} are polynomials of degree pp and qq chosen so that exp⁡(z)=Rp,q(z)+O(zp+q+1)\exp(z)=R_{p,q}(z)+O(z^{p+q+1}) [14, 9]. In the present work we restrict attention to the diagonal family Rq,qR_{q,q}, for which p=qp=q. A key property of this family is that the denominator is entirely determined by the numerator via Qq,q(z)=Pq,q(−z)Q_{q,q}(z)=P_{q,q}(-z), so that the rational approximant takes the form

Rq,q(z)=Pq(z)Pq(−z),(7)R_{q,q}(z)=\frac{P_q(z)}{P_q(-z)}, \tag*{(7)}

where we adopt the shorthand Pq≡Pq,qP_q\equiv P_{q,q}, defined by

Pq(z)=∑i=0q(2q−i)! q!(2q)!(q−i)! i!zi.(8)P_q(z)=\sum_{i=0}^{q}\frac{(2q-i)!\,q!}{(2q)!(q-i)!\,i!}z^i. \tag*{(8)}

Applied to the propagation problem (4), this gives U(δt)=Rq,q(−i δt H)+O(δt2q+1)U(\delta t)=R_{q,q}(-\mathrm{i}\,\delta t\,\mathbb{H})+O(\delta t^{2q+1}), achieving order 2q2q accuracy from a single polynomial PqP_q of degree qq. The diagonal Padé polynomials PqP_q are listed in Table 1 for q=1,…,5q=1,\ldots,5.

qqPq(z)P_q(z)kkαq(k)\alpha_q^{(k)}Order
11+12z1+\frac{1}{2}z112\frac{1}{2}2
21+12z+112z21+\frac{1}{2}z+\frac{1}{12}z^2114(1+i3)\frac{1}{4}\left(1+\frac{i}{\sqrt{3}}\right)4
21+12z+112z21+\frac{1}{2}z+\frac{1}{12}z^2214(1−i3)\frac{1}{4}\left(1-\frac{i}{\sqrt{3}}\right)4
31+12z+110z2+1120z31+\frac{1}{2}z+\frac{1}{10}z^2+\frac{1}{120}z^310.21531442311611220.21531442311611226
31+12z+110z2+1120z31+\frac{1}{2}z+\frac{1}{10}z^2+\frac{1}{120}z^320.1423427884419439+i 0.13579992570815380.1423427884419439+i\,0.13579992570815386
31+12z+110z2+1120z31+\frac{1}{2}z+\frac{1}{10}z^2+\frac{1}{120}z^330.1423427884419439−i 0.13579992570815380.1423427884419439-i\,0.13579992570815386
41+12z+328z2+184z3+11680z41+\frac{1}{2}z+\frac{3}{28}z^2+\frac{1}{84}z^3+\frac{1}{1680}z^410.1584337597342824+i 0.04744101257110840.1584337597342824+i\,0.04744101257110848
41+12z+328z2+184z3+11680z41+\frac{1}{2}z+\frac{3}{28}z^2+\frac{1}{84}z^3+\frac{1}{1680}z^420.1584337597342824−i 0.04744101257110840.1584337597342824-i\,0.04744101257110848
41+12z+328z2+184z3+11680z41+\frac{1}{2}z+\frac{3}{28}z^2+\frac{1}{84}z^3+\frac{1}{1680}z^430.0915662402657176+i 0.11566261301312760.0915662402657176+i\,0.11566261301312768
41+12z+328z2+184z3+11680z41+\frac{1}{2}z+\frac{3}{28}z^2+\frac{1}{84}z^3+\frac{1}{1680}z^440.0915662402657176−i 0.11566261301312760.0915662402657176-i\,0.11566261301312768
51+12z+215z2+160z3+1840z4+130240z51+\frac{1}{2}z+\frac{2}{15}z^2+\frac{1}{60}z^3+\frac{1}{840}z^4+\frac{1}{30240}z^510.13710881296519230.137108812965192310
51+12z+215z2+160z3+1840z4+130240z51+\frac{1}{2}z+\frac{2}{15}z^2+\frac{1}{60}z^3+\frac{1}{840}z^4+\frac{1}{30240}z^520.1174272543596986+i 0.06104970381853820.1174272543596986+i\,0.061049703818538210
51+12z+215z2+160z3+1840z4+130240z51+\frac{1}{2}z+\frac{2}{15}z^2+\frac{1}{60}z^3+\frac{1}{840}z^4+\frac{1}{30240}z^530.1174272543596986−i 0.06104970381853820.1174272543596986-i\,0.061049703818538210
51+12z+215z2+160z3+1840z4+130240z51+\frac{1}{2}z+\frac{2}{15}z^2+\frac{1}{60}z^3+\frac{1}{840}z^4+\frac{1}{30240}z^540.0640183391577052+i 0.09834106917310920.0640183391577052+i\,0.098341069173109210
51+12z+215z2+160z3+1840z4+130240z51+\frac{1}{2}z+\frac{2}{15}z^2+\frac{1}{60}z^3+\frac{1}{840}z^4+\frac{1}{30240}z^550.0640183391577052−i 0.09834106917310920.0640183391577052-i\,0.098341069173109210
⋮\vdots⋮\vdots⋮\vdots⋮\vdots⋮\vdots

Table 1. Diagonal Padé polynomials Pq(z)≡Pq,q(z)P_q(z)\equiv P_{q,q}(z) defined by Eq. (8), their coefficients αq(k)\alpha_q^{(k)} defined by Eq. (10) (16 decimal digits), and the resulting approximation order 2q2q. Complex coefficients appear in conjugate pairs. At q=1q=1 the method reduces to the standard CN scheme.

Factorization and root computation

The polynomial Pq(z)P_q(z) can be factorized as

Pq(z)=∏k=1q[1+αq(k)z],q≥1,(9)P_q(z)=\prod_{k=1}^{q}\left[1+\alpha_q^{(k)}z\right],\qquad q\geq1, \tag*{(9)}

where αq(k)∈C\alpha_q^{(k)}\in\mathbb{C} are the negated reciprocals of the roots zq(k)z_q^{(k)} of PqP_q,

αq(k)=−1zq(k),(10)\alpha_q^{(k)}=-\frac{1}{z_q^{(k)}}, \tag*{(10)}

computed to arbitrary precision by any standard polynomial root-finding algorithm. The factorized form immediately shows that Pq(0)=1P_q(0)=1, consistent with Eq. (8). The following Mathematica code computes the αq(k)\alpha_q^{(k)} to 16 decimal digits for any order qq:

Listing 1: Mathematica code for computing the Padé roots αq(k)\alpha_q^{(k)} to 16 decimal digits. The output matches Table 1.

NOrder = 5; (* Padé order q *)
NAccuracy = 16; (* number of decimal digits *)
coeffs = Table[
  Binomial[NOrder, j] / (Binomial[2*NOrder, j] * j!),
  {j, 1, NOrder}
];

poly = 1 + Sum[coeffs[[j]] * z^j, {j, 1, NOrder}];
roots = z /. NSolve[poly == 0, z, NAccuracy];
values = N[-1/roots, NAccuracy];

values // MatrixForm

The αq(k)\alpha_q^{(k)} satisfy two general properties that are useful both for verification and for the unitarity proof below. First, since PqP_q has real coefficients, complex roots appear in conjugate pairs,

αq(k+1)=[αq(k)]∗(11)\alpha_q^{(k+1)}=\left[\alpha_q^{(k)}\right]^* \tag*{(11)}

so that for odd qq there is exactly one real root and (q−1)/2(q-1)/2 conjugate pairs, while for even qq all q/2q/2 roots are complex conjugate pairs. Second, identifying the coefficient of z1z^1 in Eqs. (8) and (9) gives

∑k=1qαq(k)=12,(12)\sum_{k=1}^{q}\alpha_q^{(k)}=\frac{1}{2}, \tag*{(12)}

which provides a useful numerical check: For q=1q=1, α1(1)=1/2\alpha_1^{(1)}=1/2 exactly, while for q=2q=2, the two roots α2(1,2)=(1±i/3)/4\alpha_2^{(1,2)}=(1\pm i/\sqrt{3})/4 obviously satisfy Eq. (12) exactly. The values of αq(k)\alpha_q^{(k)} for q=1,…,5q=1,\ldots,5 are listed in Table 1.

Factored Padé propagator

With the factorization (9) in hand, the propagation step u≈U(δt)v\mathbf{u}\approx U(\delta t)\mathbf{v} can be written in high-order CN form

∏k=1q[1+αq(k)(i δt H)]u=∏k=1q[1−αq(k)(i δt H)]v,(13)\prod_{k=1}^{q}\left[1+\alpha_q^{(k)}(i\,\delta t\,\mathsf{H})\right]\mathbf{u} = \prod_{k=1}^{q}\left[1-\alpha_q^{(k)}(i\,\delta t\,\mathsf{H})\right]\mathbf{v}, \tag*{(13)}

or equivalently Pq(i δt H)u=Pq(−i δt H)vP_q(i\,\delta t\,\mathsf{H})\mathbf{u}=P_q(-i\,\delta t\,\mathsf{H})\mathbf{v}. For q=1q=1, this reduces exactly to the standard CN equation (6). For higher values of qq, the right-hand side is evaluated first as a sequence of qq tridiagonal matrix–vector multiplications, then the left-hand side is solved as a sequence of qq tridiagonal linear systems via the Thomas algorithm. Thus, it remains identical in structure to CN but extended to order 2q2q at a cost of O(qN)O(qN) operations. The formal properties of this propagator are established in Theorem 1 below, using the compact symmetric form U~q=[Pq(i δt H)]−1Pq(−i δt H)\widetilde{U}_q=[P_q(i\,\delta t\,\mathsf{H})]^{-1}P_q(-i\,\delta t\,\mathsf{H}), which follows from the commutativity of all factors.

Theorem 1. Let H∈CN×N\mathsf{H}\in\mathbb{C}^{N\times N} be a Hermitian tridiagonal matrix, let δt∈R\delta t\in\mathbb{R} (the time step may be negative), and let αq(1),…,αq(q)\alpha_q^{(1)},\ldots,\alpha_q^{(q)} be defined by Eq. (10) from the roots of PqP_q as given by Eq. (9). Since all factors [1±αq(k)i δt H]\left[1\pm\alpha_q^{(k)}i\,\delta t\,\mathsf{H}\right] are functions of the same operator H\mathsf{H}, they mutually commute, and the propagator (13) can be written in the symmetric form

U~q(δt)=[Pq(i δt H)]−1Pq(−i δt H),(14)\widetilde{U}_q(\delta t)=\left[P_q(i\,\delta t\,\mathsf{H})\right]^{-1}P_q(-i\,\delta t\,\mathsf{H}), \tag*{(14)}

where PqP_q is defined by Eq. (9). This propagator satisfies the following properties:

(i) Exact unitarity: U~q†U~q=1\widetilde{U}_q^\dagger\widetilde{U}_q = 1;

(ii) Accuracy: ∥U~q−U∥=O(δt2q+1)\left\| \widetilde{U}_q - U \right\| = O(\delta t^{2q+1});

(iii) Linear complexity: Each factor [1±αq(k)iδt H]\left[1 \pm\alpha_q^{(k)} i \delta t\,\mathbb{H}\right] is tridiagonal, so that U~qv\widetilde{U}_q \mathbf{v} is obtained from qq tridiagonal matrix–vector products and qq tridiagonal solves (Thomas algorithm), each costing O(N)O(N) operations, i.e. O(qN)O(qN) operations in total.

Proof. We prove each property in turn.

(i) Exact unitarity. Since PqP_q has real coefficients and H\mathbb{H} is Hermitian,

[Pq(−iδt H)]†=Pq(iδt H),\left[P_q(-i\delta t\,\mathbb{H})\right]^\dagger= P_q(i\delta t\,\mathbb{H}),

and therefore

U~q†=[Pq(−iδt H)]†[Pq(iδt H)]−†=Pq(iδt H)[Pq(−iδt H)]−1=U~q−1,\widetilde{U}_q^\dagger= \left[P_q(-i\delta t\,\mathbb{H})\right]^{\dagger}\left[P_q(i\delta t\,\mathbb{H})\right]^{-\dagger} = P_q(i\delta t\,\mathbb{H})\left[P_q(-i\delta t\,\mathbb{H})\right]^{-1} = \widetilde{U}_q^{-1},

so U~q†U~q=1\widetilde{U}_q^\dagger\widetilde{U}_q = 1. □

(ii) Accuracy. Setting z=−iδt Hz=-i\delta t\,\mathbb{H}, the form (14) gives U~q=Pq(−z)−1Pq(z)=Rq,q(z)=Rq,q(−iδt H)\widetilde{U}_q=P_q(-z)^{-1}P_q(z)=R_{q,q}(z)=R_{q,q}(-i\delta t\,\mathbb{H}) (cf. Eq. (7)). By definition of the diagonal Padé approximant, exp⁡(z)=Rq,q(z)+O(z2q+1)\exp(z)=R_{q,q}(z)+O(z^{2q+1}) ([9]), and therefore

∥U~q−U∥=O(δt2q+1).\left\| \widetilde{U}_q-U\right\|=O(\delta t^{2q+1}).

□

(iii) Linear complexity. Since H\mathbb{H} is tridiagonal, this structure is conserved in each factor 1±αq(k)iδt H1\pm\alpha_q^{(k)}i\delta t\,\mathbb{H}. A tridiagonal matrix–vector product costs O(N)O(N) operations, and so does a tridiagonal linear solve via the Thomas algorithm. The product (13) consists of qq such products and qq such solves, so the total cost of U~qv\widetilde{U}_q\mathbf{v} is O(qN)O(qN). □

Remark 1. The roots zq(k)z_q^{(k)} of Pq(z)P_q(z) all have strictly negative real part for any q≥1q\geq1, so that Re⁡(αq(k))>0\operatorname{Re}(\alpha_q^{(k)})>0 for all kk and qq (cf. Table 1). This follows from the A-stability of the diagonal Padé approximants Rq,qR_{q,q} ([8]): since ∣Rq,q(z)∣≤1\lvert R_{q,q}(z)\rvert\leq1 for Re⁡z≤0\operatorname{Re}z\leq0, Rq,qR_{q,q} has no poles in the closed left half-plane, i.e. Pq(−z)P_q(-z) has no roots there, and therefore all roots of Pq(z)P_q(z) lie in the open left half-plane. As a consequence, for any Hermitian H\mathbb{H} with real eigenvalues λ\lambda and any δt>0\delta t>0, the eigenvalues 1+iαq(k)δt λ1+i\alpha_q^{(k)}\delta t\,\lambda of 1+αq(k)iδt H1+\alpha_q^{(k)}i\delta t\,\mathbb{H} satisfy ∣1+iαq(k)δt λ∣≥Re⁡(αq(k))/∣αq(k)∣>0\lvert1+i\alpha_q^{(k)}\delta t\,\lambda\rvert\geq\operatorname{Re}(\alpha_q^{(k)})/\lvert\alpha_q^{(k)}\rvert>0, uniformly in δt\delta t and λ\lambda. The same bound holds for every leading principal submatrix, which is of the same form with a Hermitian block of H\mathbb{H}. Hence every pivot of the Thomas algorithm is non-zero and the algorithm never breaks down, for any real δt\delta t. Together with the exact unitarity of Theorem 1(i), this makes the method unconditionally stable with respect to δt\delta t, exactly as the standard CN scheme (6) to which it reduces at q=1q=1.

Numerical experiments: One-dimensional free particle

We validate the factored Padé propagator of Section 2.3 on a one-dimensional free particle. The reference solution U(T)vU(T)\mathbf{v} is computed directly at the final time TT with the expmv algorithm of Al-Mohy and Higham [1], which evaluates the action of the matrix exponential through a truncated Taylor series with automatic selection of the degree and of the number of sub-steps. Since the same discretized Hamiltonian is used for the reference and for the propagator, the comparison isolates the temporal error of our method, down to the accuracy of the reference itself, which is a few 10−1210^{-12} here (see below).

We consider a free particle on a uniform grid of NN points with spacing δx\delta x, whose Hamiltonian is discretized by the standard second-order finite difference Laplacian,

H=−12δx2(−211−21⋱⋱⋱1−2)(15)\mathbb{H}=-\frac{1}{2\delta x^2} \begin{pmatrix} -2 & 1 & & \\ 1 & -2 & 1 & \\ & \ddots& \ddots& \ddots\\ & & 1 & -2 \end{pmatrix} \tag*{(15)}

which is Hermitian and tridiagonal, the ideal setting for the method of Section 2. The initial state is a Gaussian wavepacket centered at −5-5 a.u. of standard deviation 22 a.u. with initial wave vector kx=2k_x=2 a.u. and the total propagation time is T=4T=4 a.u. The space grid consists of 512 points centered at the origin with δx=0.1\delta x=0.1 a.u.

We apply the factored Padé propagator for q=1,2,3,4,5q=1,2,3,4,5, corresponding to the diagonal families [q,q][q,q] with approximation orders 2, 4, 6, 8, 10 respectively, over a range of time steps δt∈[10−4,4]\delta t\in[10^{-4},4] a.u. The L2L^2 error at time TT with respect to the expmv reference is shown as a function of δt\delta t in Figure 1(a), and as a function of wall-clock computation time in Figure 2. The norm conservation ∣1−∥U~qNtv∥∣\lvert1-\lVert\widetilde{U}_q^{N_t}\mathbf{v}\rVert\rvert at time TT is shown in Figure 1(b).

One-dimensional free particle: (a) $L^2$ error and (b) norm conservation

Figure 1. One-dimensional free particle (15). (a) L2L^2 error at time T=4T = 4 a.u. as a function of time step δt\delta t for the diagonal Padé families [q,q][q,q], q=1,…,5q = 1,\ldots,5. Solid lines show the theoretical slopes O(δt2q)O(\delta t^{2q}). The error saturates at ∼10−14\sim10^{-14} (double-precision machine epsilon) and increases slightly for very small δt\delta t due to floating-point accumulation. (b) Norm conservation at time T=4T = 4 a.u. as a function of time step δt\delta t. All schemes maintain norm deviation at the level of machine precision (∼10−14\sim10^{-14}) for all δt\delta t, confirming exact unitarity by construction (Theorem 1(i)). The slight increase for small δt\delta t reflects floating-point accumulation over a large number of steps.

$L^2$ error as a function of computation time for diagonal Padé families

Figure 2. L2L^2 error at time T=4T = 4 a.u. as a function of the wall-time computation for the diagonal Padé families [q,q][q,q], q=1,…,5q = 1,\ldots,5. The gray area indicates the time above which the computation takes longer than expmv function (wall-time computation: 0.018648 s).

Convergence order. Figure 1(a) confirms that the error scales as O(δt2q)O(\delta t^{2q}) for each qq, in agreement with Theorem 1(ii). The theoretical slopes 2, 4, 6, 8, 10 are shown as solid lines and match the numerical data over several decades. For small δt\delta t, all curves saturate at a common floor of ≈5×10−12\approx5\times10^{-12}, independent of both qq and δt\delta t, and hence of the number of time steps Nt=T/δtN_t=T/\delta t, which varies here from ∼40\sim40 to 4×1044\times10^4. This floor is therefore not a property of the propagator but of the reference solution: expmv evaluates the action of the exponential through a truncated Taylor series requiring a large number of matrix–vector products for the present spectral range (∥H∥T≈800\lVert\mathbb{H}\rVert T\approx800), and the accumulated rounding errors limit its accuracy to a few 10−1210^{-12} ([1]). We verified this by comparing with the exact solution obtained from the analytic eigenvectors of the discrete Laplacian (15): the expmv reference deviates from it by 5×10−125\times10^{-12}, whereas the [5, 5] propagator with δt=0.1\delta t=0.1 a.u. deviates by only 2×10−132\times10^{-13}.

Norm conservation. Figure 1(b) shows the norm deviation ∣1−∥U~qNtv∥∣\lvert1-\lVert\widetilde{U}_q^{N_t}\mathbf{v}\rVert\rvert. It increases from ∼10−15\sim10^{-15} for the largest time steps to ∼10−11\sim10^{-11} at δt=10−4\delta t=10^{-4} a.u., roughly in proportion to NtN_t, for all qq. Since U~q\widetilde{U}_q is exactly unitary (Theorem 1(i)), this deviation is entirely due to floating-point arithmetic: each time step introduces a relative error of the order of the machine epsilon ϵ≈1.1×10−16\epsilon\approx1.1 \times10^{-16}, and these errors accumulate linearly over the NtN_t steps. The same accumulation contributes to the error of Figure 1(a), but remains below the floor set by the reference solution, except at the smallest time steps where both reach ∼10−11\sim10^{-11}. Rounding accumulation thus favours large time steps, and hence high orders: extrapolating the O(δt2)O(\delta t^2) slope, the standard CN scheme (q=1q = 1) would require Nt∼107N_t \sim10^7 steps to reach the reference floor, at which point the accumulated rounding error (∼Ntϵ\sim N_t\epsilon) would already exceed 10−1010^{-10}.

Optimal operating point. Combining these observations, the optimal strategy is to use the largest available qq with the largest δt\delta t that keeps the error at the desired level. For the present experiment, the [5,5][5, 5] propagator with δt≈0.1\delta t \approx0.1 a.u. reaches the accuracy floor of the reference solution with only Nt=40N_t = 40 time steps, which also minimizes the accumulated rounding error and the computation time.

Extension to higher-dimensional systems and split-operator methods

The method of § 2 applies directly to any Hermitian tridiagonal matrix H\mathbb{H}. Many Hamiltonians of interest are not tridiagonal, but can be written as a sum

H=∑i=1SHi,(16)\mathbb{H} = \sum_{i=1}^{S} \mathbb{H}_i, \tag*{(16)}

of Hermitian contributions Hi∈CN×N\mathbb{H}_i \in\mathbb{C}^{N \times N} that are each tridiagonal, up to a fixed ordering of the grid points, or diagonal. On a dd-dimensional grid, the kinetic energy splits into one operator per direction, each consisting of independent one-dimensional tridiagonal blocks, while the potential is diagonal and its exponential is applied exactly. Similarly, a (2M+1)(2M + 1)-point finite-difference Laplacian in one dimension is a sum of MM operators coupling sites at distance m=1,…,Mm = 1, \ldots, M. Since the Hi\mathbb{H}_i generally do not commute, we combine the factored Padé propagator with high-order operator splitting, retaining exact unitarity and O(qN)O(qN) scaling per time step.

The split-operator method

The naive factorization U(δt)=∏iexp⁡(−iδtHi)U(\delta t) = \prod_i \exp(-i \delta t \mathbb{H}_i) fails: the Baker–Campbell–Hausdorff formula gives correction terms proportional to commutators [Hi,Hj][\mathbb{H}_i, \mathbb{H}_j] and higher. Following McLachlan [12], we define the elementary maps

χ(h)=e−iH1he−iH2h⋯e−iHSh,(17)\chi(h) = e^{-i\mathbb{H}_1h}e^{-i\mathbb{H}_2h}\cdots e^{-i\mathbb{H}_Sh}, \tag*{(17)}
χ⋆(h)=e−iHSh⋯e−iH2he−iH1h,(18)\chi^\star(h) = e^{-i\mathbb{H}_Sh}\cdots e^{-i\mathbb{H}_2h}e^{-i\mathbb{H}_1h}, \tag*{(18)}

where χ⋆(h)=[χ(−h)]−1\chi^\star(h) = [\chi(-h)]^{-1} denotes the adjoint method of χ(h)\chi(h) [11, 7, 12]. For a product of operator exponentials, it amounts to reversing their order. The propagator over one time step is then approximated as

U(δt)=Us(δt)+O(δtr+1),(19)U(\delta t) = U_s(\delta t) + O(\delta t^{r+1}), \tag*{(19)}

by the composition

Us(δt)=χ(β1δt)χ⋆(β2δt)χ(β3δt)χ⋆(β4δt)⋯χ⋆(β2Nsδt),(20)U_s(\delta t) = \chi(\beta_1\delta t)\chi^\star(\beta_2\delta t)\chi(\beta_3\delta t)\chi^\star(\beta_4\delta t)\cdots\chi^\star(\beta_{2N_s}\delta t), \tag*{(20)}

where the coefficients {βs}s=1Ns\{\beta_s\}_{s=1}^{N_s} are chosen to satisfy the order conditions up to a given order rr, and the full sequence of 2Ns2N_s stages is obtained by palindromic reflection

β2Ns+1−s=βs,s=1,…,Ns,(21)\beta_{2N_s+1-s} = \beta_s,\qquad s = 1,\ldots,N_s, \tag*{(21)}

which guarantees time-reversibility and exact unitarity of the full propagator. Table 2 lists them for the Verlet (also known Strang splitting or leapfrog), BM4 and BM6 schemes. A key advantage of this formulation [12] is that the coefficients {βs}\{\beta_s\} are independent of the number of operators SS in the decomposition (16). The same table applies whether S=2S = 2 (standard two-dimensional problem), S=3S = 3 (three-dimensional problem), or any larger SS, with no re-optimization required.

ssVerletBM4BM6
11/21/20.07920369643119570.050262764400392
2—0.13031141018216630.098553683500650
3—0.22286149586760770.314960616927694
4—−0.3667132690474257−0.447346482695478
5—0.32464818868970620.492426372489876
6—0.1096884778767498−0.425118767797691
7——0.237063913978122
8——0.195602488600053
9——0.346358189850727
10——−0.362762779254345
NsN_s1610
Order246

Table 2. Independent splitting coefficients βs\beta_s for s=1,…,Nss = 1, \ldots, N_s, following the χ/χ⋆\chi/\chi^\star convention of McLachlan [12]. The full sequence of 2Ns2N_s stages is recovered by palindromic reflection (21).

The combined algorithm

Each elementary factor exp⁡(−iβsδt Hi)\exp(-i\beta_s\delta t\,\mathbb{H}_i) in Eqs. (17) and (18) is the exponential of a scaled Hermitian matrix that is tridiagonal, up to a fixed ordering of the grid points, or diagonal. Diagonal contributions, such as the potential, are exponentiated exactly. For the tridiagonal ones, we use the factored Padé propagator of § 2 with effective time step h=βsδth = \beta_s\delta t, which we denote

U~q(h,Hi)=∏k=1q[1+αq(k)(ihHi)]−1[1−αq(k)(ihHi)],(22)\widetilde{U}_q(h,\mathbb{H}_i) = \prod_{k=1}^{q}\left[1+\alpha_q^{(k)}(ih\mathbb{H}_i)\right]^{-1}\left[1-\alpha_q^{(k)}(ih\mathbb{H}_i)\right], \tag*{(22)}

with U~q(h,Hi)≈exp⁡(−ihHi)\widetilde{U}_q(h,\mathbb{H}_i) \approx\exp(-ih\mathbb{H}_i) so that U~q(δt)\widetilde{U}_q(\delta t) of § 2 corresponds to U~q(δt,H)\widetilde{U}_q(\delta t,\mathbb{H}). By Theorem 1(iii), each elementary propagator U~q(h,Hi)\widetilde{U}_q(h,\mathbb{H}_i) costs O(qN)O(qN) operations. This remains true when Hi\mathbb{H}_i is tridiagonal only up to a permutation of the grid points (Remark 2).

Algorithm 1: Solves the MM-shifted banded system Ax=dAx=d in O(N)O(N) operations. At M=1M=1 this reduces to the standard Thomas algorithm.

1 Algorithm: Strided Thomas Algorithm for M-shifted banded systems
Input: Main diagonal b ∈ ℂ^N,
Sub-diagonal a ∈ ℂ^{N−M} (entries at positions M + 1, M + 2, …, N),
Super-diagonal c ∈ ℂ^{N−M} (entries at positions 1, 2, …, N − M),
Right-hand side d ∈ ℂ^N
Output: Solution vector x ∈ ℂ^N, overwriting d

// Allocate modified super-diagonal
   (stride-aware)
2  c′ ← 0 ∈ ℂ^{N−M}

// Loop over the M independent subsystems, NO
   re-indexing needed
3  for k = 1 to M do
      // — Forward sweep for subsystem k, stride
         M —
4     c′_k ← c_k/b_k
5     d_k ← d_k/b_k
6     for i = k + M, k + 2M, … ≤ N do
7        w ← a_{i−M} · c′_{i−M}
8        denom ← b_i − a_{i−M} · c′_{i−M}
9        if i ≤ N − M then
10          c′_i ← c_i/denom
11       d_i ← (d_i − a_{i−M} · d_{i−M})/denom

      // — Backward substitution for subsystem k,
         stride M —
      // Last index of subsystem k
12    ℓ ← k + M · ⌊(N − k)/M⌋
13    x_ℓ ← d_ℓ
14    for i = ℓ − M, ℓ − 2M, … ≥ k do
15       x_i ← d_i − c′_i · x_{i+M}

Remark 2

In general, an operator Hi\mathbb{H}_i in Eq. (16) is tridiagonal only up to a fixed permutation of the grid points. A frequent case is that of an MM-shifted tridiagonal matrix, whose non-zero entries lie on the main diagonal and on the diagonals at offsets ±M\pm M. Such a matrix decouples into MM independent tridiagonal systems, formed by the entries {k,k+M,k+2M,…}\{k,k+M,k+2M,\ldots\} for k=1,…,Mk=1,\ldots,M. Algorithm 1 solves them directly on the original vector by running the Thomas algorithm on every MM-th entry (a strided access), without copying or reordering the data. Its cost is O(N)O(N) regardless of MM, and it reduces to the standard Thomas algorithm at M=1M=1. The same strided access applies to the tridiagonal matrix–vector products, so that each elementary propagator (h,Hi)(h,\mathbb{H}_i) costs O(qN)O(qN) operations.

Remark 3

The Thomas algorithm is inherently sequential, so that no parallelism is available for a single tridiagonal system. However, whenever an operator Hi\mathbb{H}_i decouples into nn independent tridiagonal systems, as for an MM-shifted matrix (n=Mn=M, Remark 2) or a block-diagonal matrix with tridiagonal blocks, the elementary propagator U~q(h,Hi)\widetilde{U}_q(h,\mathbb{H}_i) splits into nn independent problems, each requiring qq tridiagonal products and qq Thomas solves. These problems are embarrassingly parallel and map directly onto shared-memory (OpenMP), distributed-memory (MPI) or GPU (batched Thomas) architectures, while diagonal contributions reduce to elementwise multiplications. The sequential work is confined to each individual system, of size N/nN/n, and is a negligible fraction of the O(qN)O(qN) total when nn is large. This situation is generic on multi-dimensional grids, where each directional operator decouples into one independent system per grid line, and provides an additional incentive to combine the factored Padé propagator with operator splitting.

Splitting schemes of order r>2r>2 contain negative coefficients βs\beta_s (see Table 2), so that some elementary propagators are applied with a negative time step h<0h<0. For the Schrödinger equation this is harmless: Theorem 1 holds for any real time step, so each factor U~q(βsδt,Hi)\widetilde{U}_q(\beta_s\delta t,\mathbb{H}_i) remains exactly unitary and well defined, whatever the sign of βs\beta_s. Negative coefficients would instead be problematic for dissipative problems, such as imaginary-time propagation or Hamiltonians with complex absorbing potentials, for which backward sub-steps amplify the solution.

The full algorithm is given in Algorithm 2. Its properties follow directly from Theorem 1 and the splitting approximation (20):

Proposition 2. Let U~q(h,Hi)\widetilde{U}_q(h,\mathbb{H}_i) be given by Eq. (22), replaced by the exact exponential when Hi\mathbb{H}_i is diagonal, and define

V~q(h)=U~q(h,H1)U~q(h,H2)⋯U~q(h,HNs),(23)\widetilde{\mathcal{V}}_q(h)=\widetilde{U}_q(h,\mathbb{H}_1)\widetilde{U}_q(h,\mathbb{H}_2)\cdots\widetilde{U}_q(h,\mathbb{H}_{N_s}), \tag*{(23)}
V~q⋆(h)=U~q(h,HNs)⋯U~q(h,H2)U~q(h,H1).(24)\widetilde{\mathcal{V}}_q^\star(h)=\widetilde{U}_q(h,\mathbb{H}_{N_s})\cdots\widetilde{U}_q(h,\mathbb{H}_2)\widetilde{U}_q(h,\mathbb{H}_1). \tag*{(24)}

If the coefficients {βs}\{\beta_s\} make the composition (20) of order rr, the combined propagator

Vq(δt)=V~q(β1δt)V~q⋆(β2δt)⋯V~q⋆(β2Nsδt)(25)\mathcal{V}_q(\delta t)=\widetilde{\mathcal{V}}_q(\beta_1\delta t)\widetilde{\mathcal{V}}_q^\star(\beta_2\delta t)\cdots\widetilde{\mathcal{V}}_q^\star(\beta_{2N_s}\delta t) \tag*{(25)}

satisfies, for every q≥1q\geq1:

(i) Accuracy: Vq(δt)=e−iδtH+O(δtr+1)\mathcal{V}_q(\delta t)=e^{-i\delta t\mathbb{H}}+O(\delta t^{r+1}), and the global error after Nt=T/δtN_t=T/\delta t steps is O(δtr)O(\delta t^r);

(ii) Exact unitarity: Vq†Vq=1\mathcal{V}_q^\dagger\mathcal{V}_q=1;

(iii) Complexity: the cost per time step is O(q S Ns N)O(q\,S\,N_s\,N), i.e. O(N)O(N) for fixed qq, SS and NsN_s.

Proof. (i) Since all factors in Eq. (22) commute,

U~q(−h,Hi)=[Pq(−ihHi)]−1Pq(ihHi)=[U~q(h,Hi)]−1,(26)\widetilde{U}_q(-h,\mathbb{H}_i)=\left[P_q(-ih\mathbb{H}_i)\right]^{-1}P_q(ih\mathbb{H}_i)=\left[\widetilde{U}_q(h,\mathbb{H}_i)\right]^{-1}, \tag*{(26)}

i.e. each elementary propagator is time-symmetric, as is the exact exponential. Consequently [χ~q(−h)]−1=χ~q(h)[\widetilde{\chi}_q(-h)]^{-1}=\widetilde{\chi}_q(h), so that χ~q∗\widetilde{\chi}_q^* is exactly the adjoint of χ~q\widetilde{\chi}_q. Moreover, χ~q(h)=e−ihH+O(h2)\widetilde{\chi}_q(h)=e^{-ih\mathbb{H}}+O(h^2), so χ~q\widetilde{\chi}_q is a consistent first-order method. Equation (25) is therefore the composition of a first-order method and its adjoint, with unchanged coefficients {βs}\{\beta_s\}. The order conditions of such compositions involve only the βs\beta_s and are independent of the underlying method [11, 7]. This is precisely what makes the coefficients of Table 2 valid for any SS [12]. The order rr is thus preserved. Since U~q\widetilde{U}_q is unitary by (ii), local errors accumulate at most linearly over the NtN_t steps, giving a global error O(δtr)O(\delta t^r). □

(ii) Each factor U~(βsδt,Hi)\widetilde{U}(\beta_s\delta t,\mathbb{H}_i) is exactly unitary for any real time step by Theorem 1(i), and so is the exact exponential of a diagonal Hermitian matrix; a product of unitary matrices is unitary. □

(iii) A time step consists of 2Ns2N_s stages, each applying SS elementary propagators of cost O(qN)O(qN) (Remark 2). □

Remark 4. The Padé order qq thus enters only through the error constant. Since Rq,q(−z)=1/Rq,q(z)R_{q,q}(-z)=1/R_{q,q}(z), the function log⁡Rq,q\log R_{q,q} is odd,

log⁡Rq,q(z)=z+(−1)q+1(q!)2(2q)!(2q+1)!z2q+1+O(z2q+3),(27)\log R_{q,q}(z)=z+(-1)^{q+1}\frac{(q!)^2}{(2q)!(2q+1)!}z^{2q+1}+O(z^{2q+3}), \tag*{(27)}

and, for commuting Hi\mathbb{H}_i, the Padé deviations add up in log⁡Uq\log U_q with weight ∑s=12Nsβs2q+1\sum_{s=1}^{2N_s}\beta_s^{2q+1}. This sum vanishes whenever 2q+1<r2q+1<r, since ∑sβs3=0\sum_s\beta_s^3=0 (for r≥4r\ge4) and ∑sβs5=0\sum_s\beta_s^5=0 (for r≥6r\ge6) are order conditions of the composition; otherwise it only modifies the error constant (e.g. ∑sβs5≠0\sum_s\beta_s^5\ne0 for BM4 with q=1q=1). We have verified this cancellation for non-commuting operators by a direct expansion in the free algebra generated by H1\mathbb{H}_1 and H2\mathbb{H}_2, up to fourth order for BM4 with q=1q=1. The preservation of order relies on the time symmetry (26), not on unitarity: a non-symmetric approximation of the exponential, such as a truncated Taylor series, would in general reduce the order of the composition.

Numerical experiments: Two-dimensional non-separable system

We consider a particle on a two-dimensional grid of Nx×Ny=512×512N_x\times N_y=512\times512 points with spacings δx=δy=0.1\delta x=\delta y=0.1 a.u., centered at the origin, with Hamiltonian H=Kx+Ky+V\mathbb{H}=\mathbb{K}_x+\mathbb{K}_y+\mathbb{V}. The kinetic operators Kx\mathbb{K}_x and Ky\mathbb{K}_y are discretized by the second-order finite-difference Laplacian (15) along each direction, and V\mathbb{V} is the diagonal matrix of the Gaussian potential

V(x,y)=exp⁡(−ωxx2−ωyy2+λxy)(28)V(x,y)=\exp(-\omega_xx^2-\omega_yy^2+\lambda xy) \tag*{(28)}

evaluated on the grid, with ωx=ωy=0.5\omega_x=\omega_y=0.5 and λ=0.3\lambda=0.3. Since VV is not of the additive form Vx(x)+Vy(y)V_x(x)+V_y(y), the Hamiltonian cannot be written as a sum of commuting one-dimensional operators, and the splitting is genuinely required. The initial Gaussian wavepacket, centered at (x0,y0)=(−5,−5)(x_0,y_0)=(-5,-5) a.u. with momenta (kx0,ky0)=(2,2)(k_{x0},k_{y0})=(2,2) a.u. and widths (σx,σy)=(2,2)(\sigma_x,\sigma_y)=(2,2) a.u., is propagated to T=4T=4 a.u.

We use the decomposition (16) with S=3S=3, (H1,H2,H3)=(Kx,Ky,V)(\mathbb{H}_1,\mathbb{H}_2,\mathbb{H}_3)=(\mathbb{K}_x,\mathbb{K}_y,\mathbb{V}). With the grid points stored in lexicographic order (xx fastest), Kx\mathbb{K}_x is tridiagonal, while Ky\mathbb{K}_y couples entries separated by NxN_x. It is therefore NxN_x-shifted and handled by Algorithm 1 with M=NxM=N_x (Remark 2). Both operators thus decouple into one independent tridiagonal system per grid line, NyN_y and NxN_x respectively, which can be solved in parallel. The diagonal factor exp⁡(−iβsδt V)\exp(-i\beta_s\delta t\,\mathbb{V}) is applied exactly. The reference solution is again computed with exp⁡m\exp_m applied to the full two-dimensional Hamiltonian.

Figure 3(a) shows the L2L^2 error at time TT as a function of δt\delta t for the Verlet, BM4 and BM6 schemes and q=1,…,5q=1,\ldots,5. In all cases the convergence slope equals the splitting order rr, independently of qq, as predicted by Proposition 2(i). The Padé order only affects the error constant. More precisely, since each time step is time-symmetric, the Padé correction first contributes to the local error at order δt2q+1\delta t^{2q+1}. For q≤r/2q\le r/2 it therefore enters at the same order as the splitting error, δtr+1\delta t^{r+1}, and increases the error constant, whereas for q≥r/2+1q\ge r/2+1 it is of higher order and the curves coincide with that of the splitting with exact exponentials. This is clearly visible in Figure 3(a): the curves with q≥2q\ge2 coincide for Verlet, q≥3q\ge3 for BM4 and q≥4q\ge4 for BM6. For BM4 and BM6, the error saturates at ∼10−11\sim10^{-11} for small δt\delta t. As in § 2.4, this floor is independent of qq and of the scheme, and is consistent with the accuracy of the exp⁡m\exp_m reference, here for a larger spectral range (∥H∥T≈1600\lVert\mathbb{H}\rVert T\approx1600).

Two-dimensional particle with the non-separable potential

Figure 3. Two-dimensional particle with the non-separable potential (28). (a) L2L^2 error at time T=4T = 4 a.u. as a function of the time step δt\delta t for the diagonal Padé families [q,q][q,q], q=1,…,5q = 1,\ldots,5, combined with the Verlet (a1), BM4 (a2) and BM6 (a3) splitting schemes. Solid lines show the scaling ∝δtr\propto\delta t^r of the splitting, with r=2r = 2 (a1), 44 (a2) and 66 (a3). Curves with q≥r/2+1q \ge r/2 + 1 coincide. The error saturates at ∼10−11\sim10^{-11}, the accuracy of the expmv reference. (b) Norm deviation at time TT as a function of δt\delta t; its increase for small δt\delta t reflects the accumulation of rounding errors over the Nt=T/δtN_t = T/\delta t steps.

Figure 3(b) shows the norm deviation. It remains ∼10−13\sim10^{-13} for δt≳10−2\delta t\gtrsim10^{-2} a.u. and increases to ∼10−10\sim10^{-10} at δt=10−4\delta t=10^{-4} a.u., for all qq and all schemes. As in § 2.4, this growth is due to the accumulation of rounding errors over the Nt=T/δtN_t=T/\delta t steps, the propagator being exactly unitary (Proposition 2(ii)).

These results show that, in the presence of splitting, increasing qq beyond r/2+1r/2+1 brings no further gain in accuracy, since the error is then entirely due to the splitting. Conversely, q≤r/2q\le r/2 yields a larger error constant, which must be compensated by a smaller time step. The choice q=r/2+1q=r/2+1 (i.e. q=2q=2, 3 and 4 for Verlet, BM4 and BM6, respectively) therefore reaches the accuracy of the underlying splitting scheme at the lowest Padé order.

Conclusions

These two regimes, one-dimensional propagation without splitting and multi-dimensional propagation with splitting, call for different choices of the Padé order qq.

In one spatial dimension (§ 2.4), the Padé approximation is the only source of temporal error. The convergence order is 2q2q, so that increasing qq directly reduces the error and allows much larger time steps for a given accuracy. In multi-dimensional problems with operator splitting (§ 3.5), the convergence order is set by the splitting order rr, independently of qq. Owing to the time symmetry of the factored Padé propagator, its contributions obey the same order conditions as the splitting itself (Proposition 2), and the Padé order only affects the error constant, not the scaling. The standard CN elementary propagator (q=1q = 1) therefore suffices to reach the full order of high-order splitting schemes such as BM4 and BM6, at the lowest cost per time step. Larger qq reduces the error constant, until q≥r/2+1q \ge r/2 + 1, beyond which the error coincides with that of the splitting with exact exponentials.

This also shows that the two levels of approximation are not jointly optimized: since the overall order is fixed by the splitting, the Padé roots αq(k)\alpha_q^{(k)} represent unused degrees of freedom. A combined scheme in which the coefficients {βs}\{\beta_s\} and {αq(k)}\{\alpha_q^{(k)}\} are tuned together could reach a target global order with fewer tridiagonal operations. Deriving the corresponding joint order conditions is a natural direction for future work.

Code availability

The MATLAB implementations of the factored Padé propagator in one and two dimensions, including the computation of the reference solutions, are available at https://github.com/jonathan-dubois/High_order_Crank-Nicolson.

Data availability

The data underlying Figure 1–Figure 3 can be reproduced with the codes above.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

CRediT authorship contribution statement

Lou Freschi: Conceptualization, Methodology, Software, Formal Analysis, Investigation, Writing – Review & Editing. Camille Lévêque: Methodology, Validation, Writing – Review & Editing. Jérémie Caillat: Validation, Writing – Review & Editing. Richard Taïeb: Conceptualization, Formal Analysis, Validation, Writing – Review & Editing. Jonathan Dubois: Conceptualization, Methodology, Software, Formal Analysis, Supervision, Validation, Writing – Original Draft.

Algorithm 2: Combined propagator using the χ/χ⋆\chi/\chi^\star convention of [12]. Odd stages apply χ(β~ δt)=e−iβ~δtH1⋯e−iβ~δtHS−1e−iβ~δtV\chi(\widetilde{\beta}\,\delta t)=e^{-i\widetilde{\beta}\delta t\mathbb{H}_1}\cdots e^{-i\widetilde{\beta}\delta t\mathbb{H}_{S-1}}e^{-i\widetilde{\beta}\delta tV}; even stages apply χ⋆(β~ δt)\chi^\star(\widetilde{\beta}\,\delta t) in reversed order. The palindromic reflection (21) guarantees time-reversibility. Total cost: O(2Nsq(S−1)N)O(2N_s q (S-1)N) tridiagonal operations + O(2NsN)O(2N_sN) diagonal multiplications per time step.

  1. Algorithm: Combined split-operator / factored Padé propagator Input: State vector v=∣ψ(t)⟩\mathbf{v}=|\psi(t)\rangle, tridiagonal operators H1,…,HS−1\mathbb{H}_1,\ldots,\mathbb{H}_{S-1} and diagonal operator HS=V(x,y)\mathbb{H}_S=V(x,y), time step δt\delta t, Padé roots αq(1),…,αq(q)\alpha_q^{(1)},\ldots,\alpha_q^{(q)} (Table 1), independent splitting coefficients β1,…,βNs\beta_1,\ldots,\beta_{N_s} (Table 2) Output: u≈U(δt)v\mathbf{u}\approx U(\delta t)\mathbf{v}

    // Full palindromic sequence: β~s=βs\widetilde{\beta}_s=\beta_s for s≤Nss\leq N_s, β~s=β2Ns+1−s\widetilde{\beta}_s=\beta_{2N_s+1-s} for s>Nss>N_s

  1. u←v\mathbf{u}\leftarrow\mathbf{v}

  1. for s=1s=1 to 2Ns2N_s do

  2. &nbsp;&nbsp;&nbsp;&nbsp;if s≤Nss\leq N_s then

  3. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;β~←βs\widetilde{\beta}\leftarrow\beta_s

  4. &nbsp;&nbsp;&nbsp;&nbsp;else

  5. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;β~←β2Ns+1−s\widetilde{\beta}\leftarrow\beta_{2N_s+1-s}

  6. &nbsp;&nbsp;&nbsp;&nbsp;if ss is odd then // χ(β~ δt)\chi(\widetilde{\beta}\,\delta t): forward order

  7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for i=1i=1 to S−1S-1 do &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// Factored Padé propagator for tridiagonal Hi\mathbb{H}_i

  8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for k=1k=1 to qq do

  9. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u←[1−αq(k)iβ~ δt Hi]u\mathbf{u}\leftarrow[1-\alpha_q^{(k)}i\widetilde{\beta}\,\delta t\,\mathbb{H}_i]\mathbf{u} // tridiagonal mv, O(N)O(N)

  10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u←[1+αq(k)iβ~ δt Hi]−1u\mathbf{u}\leftarrow[1+\alpha_q^{(k)}i\widetilde{\beta}\,\delta t\,\mathbb{H}_i]^{-1}\mathbf{u} // Thomas algorithm, O(N)O(N)

  11. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u←exp⁡(−iβ~ δt V)u\mathbf{u}\leftarrow\exp(-i\widetilde{\beta}\,\delta t\,V)\mathbf{u} // diagonal: elementwise multiply, O(N)O(N)

  12. &nbsp;&nbsp;&nbsp;&nbsp;else // χ⋆(β~ δt)\chi^\star(\widetilde{\beta}\,\delta t): reversed order

  13. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u←exp⁡(−iβ~ δt V)u\mathbf{u}\leftarrow\exp(-i\widetilde{\beta}\,\delta t\,V)\mathbf{u} // diagonal: elementwise multiply, O(N)O(N)

  14. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for i=S−1,S−2,…,1i=S-1,S-2,\ldots,1 do &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;// Factored Padé propagator for tridiagonal Hi\mathbb{H}_i

  15. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for k=1k=1 to qq do

  16. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u←[1−αq(k)iβ~ δt Hi]u\mathbf{u}\leftarrow[1-\alpha_q^{(k)}i\widetilde{\beta}\,\delta t\,\mathbb{H}_i]\mathbf{u} // tridiagonal mv, O(N)O(N)

  17. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u←[1+αq(k)iβ~ δt Hi]−1u\mathbf{u}\leftarrow[1+\alpha_q^{(k)}i\widetilde{\beta}\,\delta t\,\mathbb{H}_i]^{-1}\mathbf{u} // Thomas algorithm, O(N)O(N)

  1. return u\mathbf{u}

References

  1. [1]Al-Mohy, A.H., Higham, N.J., 2011. Computing the action of the matrix exponential, with an application to exponential integrators. SIAM Journal on Scientific Computing 33, 488.
  2. [2]Anderson, J.D., 1995. Computational Fluid Dynamics: The Basics with Applications. McGraw-Hill, New York.
  3. [3]Blanes, S., Casas, F., Oteo, J., Ros, J., 2009. The magnus expansion and some of its applications. Physics Reports 470, 151.
  4. [4]Crank, J., Nicolson, P., 1947. A practical method for numerical evaluation of solutions of partial differential equations of the heat-conduction type 43, 50.DOI
  5. [5]Duffy, D.J., 2006. Finite Difference Methods in Financial Engineering: A Partial Differential Equation Approach. The Wiley Finance Series, John Wiley & Sons, Chichester, UK.
  6. [6]Golub, G.H., Van Loan, C.F., 2013. Matrix Computations - 4th Edition. Johns Hopkins University Press, Philadelphia, PA.
  7. [7]Hairer, E., Lubich, C., Wanner, G., 2006. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations. volume 31 of Springer Series in Computational Mathematics. 2 ed., Springer, Berlin.
  8. [8]Hairer, E., Wanner, G., 1996. Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems. volume 14 of Springer Series in Computational Mathematics. 2nd ed., Springer.
  9. [9]Higham, N.J., 2005. The scaling and squaring method for the matrix exponential revisited. SIAM Journal on Matrix Analysis and Applications 26, 1179.
  10. [10]Kulander, K.C., Schäfer, K.J., Krause, J.L., 1991. Single-active electron calculation of multiphoton processes in krypton. International Journal of Quantum Chemistry 40, 415–429.DOI
  11. [11]McLachlan, R.I., 1995. On the numerical integration of ordinary differential equations by symmetric composition methods. SIAM Journal on Scientific Computing 16, 151–168.DOI
  12. [12]McLachlan, R.I., 2022. Tuning symplectic integrators is easy and worthwhile. Communications in Computational Physics 31, 987.DOI
  13. [13]Murray, J.D., 2002. Mathematical Biology I: An Introduction. 3rd ed., Springer, New York.DOI
  14. [14]Padé, H., 1892. Sur la représentation approchée d’une fonction par des fractions rationnelles. Annales scientifiques de l’École Normale Supérieure 9, 3–93.
  15. [15]Park, T.J., Light, J.C., 1986. Unitary quantum time evolution by iterative lanczos reduction. The Journal of Chemical Physics 85, 5870.DOI
  16. [16]Taflove, A., Hagness, S.C., 2005. Computational Electrodynamics: The Finite-Difference Time-Domain Method. 3rd ed., Artech House, Norwood, MA.
  17. [17]Tannor, D.J., 2007. Introduction to Quantum Mechanics: A Time-Dependent Perspective. University Science Books, Sausalito, CA.
  18. [18]Wilmott, P., Dewynne, J., Howison, S., 1993. Option Pricing: Mathematical Models and Computation. Oxford Financial Press, Oxford, UK.

Paper details

vlnc:W_cqxvbjvb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents