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 of a system described by a time-independent Hamiltonian . Setting , its formal solution over a time interval reads
where is the initial state. For clarity we restrict attention to the time-independent case throughout, although the extension to time-dependent Hamiltonians is straightforward via a Magnus expansion or a piecewise-constant approximation of over each time step Blanes, Casas, Oteo and Ros, [3].
Once 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 , 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 is split into steps of size , and the evolution of the quantum state over one time-step interval reads as
with for . This partitioning strategy is closely related to the scaling and squaring approach Higham, [9], although the two settings differ fundamentally: here 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
so that Eq. (2) reads , or in vector notation
where and . The goal is to compute an approximation to satisfying
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 denotes the order of accuracy, such that can be computed efficiently for tridiagonal . 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 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 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],
which is second-order accurate in and exactly unitary for Hermitian . When is tridiagonal, both operations cost via the Thomas algorithm. However, CN is limited to second-order accuracy and no established high-order generalization that retains tridiagonal scaling exists in the literature.
Present work
The goal of this work is to preserve the efficiency of tridiagonal matrix operations while extending temporal accuracy to arbitrary order. We achieve this through two ideas. First, we employ the diagonal Padé approximant [14] , which approximates to order and is real, ensuring exact unitarity. Second, we factorize , where are the roots of . Each factor is tridiagonal whenever is tridiagonal, reducing the full propagator to sequential Thomas solves and matrix–vector products, all , for a total cost of per time step. At with 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 , with each tridiagonal or diagonal, can be handled at the same 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() and the family
The Padé approximant of order of the exponential is the rational function , where and are polynomials of degree and chosen so that [14, 9]. In the present work we restrict attention to the diagonal family , for which . A key property of this family is that the denominator is entirely determined by the numerator via , so that the rational approximant takes the form
where we adopt the shorthand , defined by
Applied to the propagation problem (4), this gives , achieving order accuracy from a single polynomial of degree . The diagonal Padé polynomials are listed in Table 1 for .
| Order | ||||
| 1 | 1 | 2 | ||
| 2 | 1 | 4 | ||
| 2 | 2 | 4 | ||
| 3 | 1 | 6 | ||
| 3 | 2 | 6 | ||
| 3 | 3 | 6 | ||
| 4 | 1 | 8 | ||
| 4 | 2 | 8 | ||
| 4 | 3 | 8 | ||
| 4 | 4 | 8 | ||
| 5 | 1 | 10 | ||
| 5 | 2 | 10 | ||
| 5 | 3 | 10 | ||
| 5 | 4 | 10 | ||
| 5 | 5 | 10 | ||
Table 1. Diagonal Padé polynomials defined by Eq. (8), their coefficients defined by Eq. (10) (16 decimal digits), and the resulting approximation order . Complex coefficients appear in conjugate pairs. At the method reduces to the standard CN scheme.
Factorization and root computation
The polynomial can be factorized as
where are the negated reciprocals of the roots of ,
computed to arbitrary precision by any standard polynomial root-finding algorithm. The factorized form immediately shows that , consistent with Eq. (8). The following Mathematica code computes the to 16 decimal digits for any order :
Listing 1: Mathematica code for computing the Padé roots 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 satisfy two general properties that are useful both for verification and for the unitarity proof below. First, since has real coefficients, complex roots appear in conjugate pairs,
so that for odd there is exactly one real root and conjugate pairs, while for even all roots are complex conjugate pairs. Second, identifying the coefficient of in Eqs. (8) and (9) gives
which provides a useful numerical check: For , exactly, while for , the two roots obviously satisfy Eq. (12) exactly. The values of for are listed in Table 1.
Factored Padé propagator
With the factorization (9) in hand, the propagation step can be written in high-order CN form
or equivalently . For , this reduces exactly to the standard CN equation (6). For higher values of , the right-hand side is evaluated first as a sequence of tridiagonal matrix–vector multiplications, then the left-hand side is solved as a sequence of tridiagonal linear systems via the Thomas algorithm. Thus, it remains identical in structure to CN but extended to order at a cost of operations. The formal properties of this propagator are established in Theorem 1 below, using the compact symmetric form , which follows from the commutativity of all factors.
Theorem 1. Let be a Hermitian tridiagonal matrix, let (the time step may be negative), and let be defined by Eq. (10) from the roots of as given by Eq. (9). Since all factors are functions of the same operator , they mutually commute, and the propagator (13) can be written in the symmetric form
where is defined by Eq. (9). This propagator satisfies the following properties:
(i) Exact unitarity: ;
(ii) Accuracy: ;
(iii) Linear complexity: Each factor is tridiagonal, so that is obtained from tridiagonal matrix–vector products and tridiagonal solves (Thomas algorithm), each costing operations, i.e. operations in total.
Proof. We prove each property in turn.
(i) Exact unitarity. Since has real coefficients and is Hermitian,
and therefore
so . □
(ii) Accuracy. Setting , the form (14) gives (cf. Eq. (7)). By definition of the diagonal Padé approximant, ([9]), and therefore
□
(iii) Linear complexity. Since is tridiagonal, this structure is conserved in each factor . A tridiagonal matrix–vector product costs operations, and so does a tridiagonal linear solve via the Thomas algorithm. The product (13) consists of such products and such solves, so the total cost of is . □
Remark 1. The roots of all have strictly negative real part for any , so that for all and (cf. Table 1). This follows from the A-stability of the diagonal Padé approximants ([8]): since for , has no poles in the closed left half-plane, i.e. has no roots there, and therefore all roots of lie in the open left half-plane. As a consequence, for any Hermitian with real eigenvalues and any , the eigenvalues of satisfy , uniformly in and . The same bound holds for every leading principal submatrix, which is of the same form with a Hermitian block of . Hence every pivot of the Thomas algorithm is non-zero and the algorithm never breaks down, for any real . Together with the exact unitarity of Theorem 1(i), this makes the method unconditionally stable with respect to , exactly as the standard CN scheme (6) to which it reduces at .
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 is computed directly at the final time 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 here (see below).
We consider a free particle on a uniform grid of points with spacing , whose Hamiltonian is discretized by the standard second-order finite difference Laplacian,
which is Hermitian and tridiagonal, the ideal setting for the method of Section 2. The initial state is a Gaussian wavepacket centered at a.u. of standard deviation a.u. with initial wave vector a.u. and the total propagation time is a.u. The space grid consists of 512 points centered at the origin with a.u.
We apply the factored Padé propagator for , corresponding to the diagonal families with approximation orders 2, 4, 6, 8, 10 respectively, over a range of time steps a.u. The error at time with respect to the expmv reference is shown as a function of in Figure 1(a), and as a function of wall-clock computation time in Figure 2. The norm conservation at time is shown in Figure 1(b).

Figure 1. One-dimensional free particle (15). (a) error at time a.u. as a function of time step for the diagonal Padé families , . Solid lines show the theoretical slopes . The error saturates at (double-precision machine epsilon) and increases slightly for very small due to floating-point accumulation. (b) Norm conservation at time a.u. as a function of time step . All schemes maintain norm deviation at the level of machine precision () for all , confirming exact unitarity by construction (Theorem 1(i)). The slight increase for small reflects floating-point accumulation over a large number of steps.

Figure 2. error at time a.u. as a function of the wall-time computation for the diagonal Padé families , . 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 for each , 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 , all curves saturate at a common floor of , independent of both and , and hence of the number of time steps , which varies here from to . 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 (), and the accumulated rounding errors limit its accuracy to a few ([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 , whereas the [5, 5] propagator with a.u. deviates by only .
Norm conservation. Figure 1(b) shows the norm deviation . It increases from for the largest time steps to at a.u., roughly in proportion to , for all . Since 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 , and these errors accumulate linearly over the 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 . Rounding accumulation thus favours large time steps, and hence high orders: extrapolating the slope, the standard CN scheme () would require steps to reach the reference floor, at which point the accumulated rounding error () would already exceed .
Optimal operating point. Combining these observations, the optimal strategy is to use the largest available with the largest that keeps the error at the desired level. For the present experiment, the propagator with a.u. reaches the accuracy floor of the reference solution with only 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 . Many Hamiltonians of interest are not tridiagonal, but can be written as a sum
of Hermitian contributions that are each tridiagonal, up to a fixed ordering of the grid points, or diagonal. On a -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 -point finite-difference Laplacian in one dimension is a sum of operators coupling sites at distance . Since the generally do not commute, we combine the factored Padé propagator with high-order operator splitting, retaining exact unitarity and scaling per time step.
The split-operator method
The naive factorization fails: the Baker–Campbell–Hausdorff formula gives correction terms proportional to commutators and higher. Following McLachlan [12], we define the elementary maps
where denotes the adjoint method of [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
by the composition
where the coefficients are chosen to satisfy the order conditions up to a given order , and the full sequence of stages is obtained by palindromic reflection
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 are independent of the number of operators in the decomposition (16). The same table applies whether (standard two-dimensional problem), (three-dimensional problem), or any larger , with no re-optimization required.
| Verlet | BM4 | BM6 | |
| 1 | 0.0792036964311957 | 0.050262764400392 | |
| 2 | — | 0.1303114101821663 | 0.098553683500650 |
| 3 | — | 0.2228614958676077 | 0.314960616927694 |
| 4 | — | −0.3667132690474257 | −0.447346482695478 |
| 5 | — | 0.3246481886897062 | 0.492426372489876 |
| 6 | — | 0.1096884778767498 | −0.425118767797691 |
| 7 | — | — | 0.237063913978122 |
| 8 | — | — | 0.195602488600053 |
| 9 | — | — | 0.346358189850727 |
| 10 | — | — | −0.362762779254345 |
| 1 | 6 | 10 | |
| Order | 2 | 4 | 6 |
Table 2. Independent splitting coefficients for , following the convention of McLachlan [12]. The full sequence of stages is recovered by palindromic reflection (21).
The combined algorithm
Each elementary factor 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 , which we denote
with so that of § 2 corresponds to . By Theorem 1(iii), each elementary propagator costs operations. This remains true when is tridiagonal only up to a permutation of the grid points (Remark 2).
Algorithm 1: Solves the -shifted banded system in operations. At 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 in Eq. (16) is tridiagonal only up to a fixed permutation of the grid points. A frequent case is that of an -shifted tridiagonal matrix, whose non-zero entries lie on the main diagonal and on the diagonals at offsets . Such a matrix decouples into independent tridiagonal systems, formed by the entries for . Algorithm 1 solves them directly on the original vector by running the Thomas algorithm on every -th entry (a strided access), without copying or reordering the data. Its cost is regardless of , and it reduces to the standard Thomas algorithm at . The same strided access applies to the tridiagonal matrix–vector products, so that each elementary propagator costs operations.
Remark 3
The Thomas algorithm is inherently sequential, so that no parallelism is available for a single tridiagonal system. However, whenever an operator decouples into independent tridiagonal systems, as for an -shifted matrix (, Remark 2) or a block-diagonal matrix with tridiagonal blocks, the elementary propagator splits into independent problems, each requiring tridiagonal products and 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 , and is a negligible fraction of the total when 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 contain negative coefficients (see Table 2), so that some elementary propagators are applied with a negative time step . For the Schrödinger equation this is harmless: Theorem 1 holds for any real time step, so each factor remains exactly unitary and well defined, whatever the sign of . 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 be given by Eq. (22), replaced by the exact exponential when is diagonal, and define
If the coefficients make the composition (20) of order , the combined propagator
satisfies, for every :
(i) Accuracy: , and the global error after steps is ;
(ii) Exact unitarity: ;
(iii) Complexity: the cost per time step is , i.e. for fixed , and .
Proof. (i) Since all factors in Eq. (22) commute,
i.e. each elementary propagator is time-symmetric, as is the exact exponential. Consequently , so that is exactly the adjoint of . Moreover, , so is a consistent first-order method. Equation (25) is therefore the composition of a first-order method and its adjoint, with unchanged coefficients . The order conditions of such compositions involve only the and are independent of the underlying method [11, 7]. This is precisely what makes the coefficients of Table 2 valid for any [12]. The order is thus preserved. Since is unitary by (ii), local errors accumulate at most linearly over the steps, giving a global error . □
(ii) Each factor 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 stages, each applying elementary propagators of cost (Remark 2). □
Remark 4. The Padé order thus enters only through the error constant. Since , the function is odd,
and, for commuting , the Padé deviations add up in with weight . This sum vanishes whenever , since (for ) and (for ) are order conditions of the composition; otherwise it only modifies the error constant (e.g. for BM4 with ). We have verified this cancellation for non-commuting operators by a direct expansion in the free algebra generated by and , up to fourth order for BM4 with . 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 points with spacings a.u., centered at the origin, with Hamiltonian . The kinetic operators and are discretized by the second-order finite-difference Laplacian (15) along each direction, and is the diagonal matrix of the Gaussian potential
evaluated on the grid, with and . Since is not of the additive form , 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 a.u. with momenta a.u. and widths a.u., is propagated to a.u.
We use the decomposition (16) with , . With the grid points stored in lexicographic order ( fastest), is tridiagonal, while couples entries separated by . It is therefore -shifted and handled by Algorithm 1 with (Remark 2). Both operators thus decouple into one independent tridiagonal system per grid line, and respectively, which can be solved in parallel. The diagonal factor is applied exactly. The reference solution is again computed with applied to the full two-dimensional Hamiltonian.
Figure 3(a) shows the error at time as a function of for the Verlet, BM4 and BM6 schemes and . In all cases the convergence slope equals the splitting order , independently of , 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 . For it therefore enters at the same order as the splitting error, , and increases the error constant, whereas for 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 coincide for Verlet, for BM4 and for BM6. For BM4 and BM6, the error saturates at for small . As in § 2.4, this floor is independent of and of the scheme, and is consistent with the accuracy of the reference, here for a larger spectral range ().

Figure 3. Two-dimensional particle with the non-separable potential (28). (a) error at time a.u. as a function of the time step for the diagonal Padé families , , combined with the Verlet (a1), BM4 (a2) and BM6 (a3) splitting schemes. Solid lines show the scaling of the splitting, with (a1), (a2) and (a3). Curves with coincide. The error saturates at , the accuracy of the expmv reference. (b) Norm deviation at time as a function of ; its increase for small reflects the accumulation of rounding errors over the steps.
Figure 3(b) shows the norm deviation. It remains for a.u. and increases to at a.u., for all and all schemes. As in § 2.4, this growth is due to the accumulation of rounding errors over the steps, the propagator being exactly unitary (Proposition 2(ii)).
These results show that, in the presence of splitting, increasing beyond brings no further gain in accuracy, since the error is then entirely due to the splitting. Conversely, yields a larger error constant, which must be compensated by a smaller time step. The choice (i.e. , 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 .
In one spatial dimension (§ 2.4), the Padé approximation is the only source of temporal error. The convergence order is , so that increasing 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 , independently of . 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 () 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 reduces the error constant, until , 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 represent unused degrees of freedom. A combined scheme in which the coefficients and 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 convention of [12]. Odd stages apply ; even stages apply in reversed order. The palindromic reflection (21) guarantees time-reversibility. Total cost: tridiagonal operations + diagonal multiplications per time step.
Algorithm: Combined split-operator / factored Padé propagator Input: State vector , tridiagonal operators and diagonal operator , time step , Padé roots (Table 1), independent splitting coefficients (Table 2) Output:
// Full palindromic sequence: for , for
for to do
if then
else
if is odd then // : forward order
for to do // Factored Padé propagator for tridiagonal
for to do
// tridiagonal mv,
// Thomas algorithm,
// diagonal: elementwise multiply,
else // : reversed order
// diagonal: elementwise multiply,
for do // Factored Padé propagator for tridiagonal
for to do
// tridiagonal mv,
// Thomas algorithm,
return
References
- [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]Anderson, J.D., 1995. Computational Fluid Dynamics: The Basics with Applications. McGraw-Hill, New York.
- [3]Blanes, S., Casas, F., Oteo, J., Ros, J., 2009. The magnus expansion and some of its applications. Physics Reports 470, 151.
- [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]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]Golub, G.H., Van Loan, C.F., 2013. Matrix Computations - 4th Edition. Johns Hopkins University Press, Philadelphia, PA.
- [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]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]Higham, N.J., 2005. The scaling and squaring method for the matrix exponential revisited. SIAM Journal on Matrix Analysis and Applications 26, 1179.
- [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]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]McLachlan, R.I., 2022. Tuning symplectic integrators is easy and worthwhile. Communications in Computational Physics 31, 987.DOI
- [13]Murray, J.D., 2002. Mathematical Biology I: An Introduction. 3rd ed., Springer, New York.DOI
- [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]Park, T.J., Light, J.C., 1986. Unitary quantum time evolution by iterative lanczos reduction. The Journal of Chemical Physics 85, 5870.DOI
- [16]Taflove, A., Hagness, S.C., 2005. Computational Electrodynamics: The Finite-Difference Time-Domain Method. 3rd ed., Artech House, Norwood, MA.
- [17]Tannor, D.J., 2007. Introduction to Quantum Mechanics: A Time-Dependent Perspective. University Science Books, Sausalito, CA.
- [18]Wilmott, P., Dewynne, J., Howison, S., 1993. Option Pricing: Mathematical Models and Computation. Oxford Financial Press, Oxford, UK.