betaFeedback

WorksMathematics

Implicit integration of nonlinear evolution equations on tensor manifolds

Abstract

Explicit step-truncation tensor methods have recently proven successful in integrating initial value problems for high-dimensional partial differential equations (PDEs). However, the combination of non-linearity and stiffness may introduce time-step restrictions which could make explicit integration computationally infeasible. To overcome this problem, we develop a new class of implicit rank-adaptive algorithms for temporal integration of nonlinear evolution equations on tensor manifolds. These algorithms are based on performing one time step with a conventional time-stepping scheme, followed by an implicit fixed point iteration step involving a rank-adaptive truncation operation onto a tensor manifold. Implicit step truncation methods are straightforward to implement as they rely only on arithmetic operations between tensors, which can be performed by efficient and scalable parallel algorithms. Numerical applications demonstrating the effectiveness of implicit step-truncation tensor integrators are presented and discussed for the Allen-Cahn equation, the Fokker-Planck equation, and the nonlinear Schrödinger equation.

Introduction

High-dimensional nonlinear evolution equations of the form

∂f(x,t)∂t=N(f(x,t),x),f(x,0)=f0(x),(1)\frac{\partial f(\boldsymbol{x},t)}{\partial t}=\mathcal{N}(f(\boldsymbol{x},t),\boldsymbol{x}), \qquad f(\boldsymbol{x},0)=f_0(\boldsymbol{x}), \tag*{(1)}

arise in many areas of mathematical physics, e.g., in statistical mechanics [7, 39], quantum field theory [50], and in the approximation of functional differential equations (infinite-dimensional PDEs) [47, 48] such as the Hopf equation of turbulence [28], or functional equations modeling deep learning [21]. In equation (1), f:Ω×[0,T]→Rf:\Omega\times[0,T]\to\mathbb{R} is a dd-dimensional time-dependent scalar field defined on the domain Ω⊆Rd\Omega\subseteq\mathbb{R}^{d} (d≥2d\geq2), TT is the period of integration, and N\mathcal{N} is a nonlinear operator which may depend on the variables x=(x1,…,xd)∈Ω\boldsymbol{x}=(x_1,\ldots,x_d)\in\Omega, and may incorporate boundary conditions. For simplicity, we assume that the domain Ω\Omega is a Cartesian product of dd one-dimensional domains Ωi\Omega_i

Ω=Ω1×⋯×Ωd,(2)\Omega=\Omega_1\times\cdots\times\Omega_d, \tag*{(2)}

and that ff is an element of a Hilbert space H(Ω;[0,T])H(\Omega;[0,T]). In these hypotheses, we can leverage the isomorphism H(Ω;[0,T])≅H([0,T])⊗H(Ω1)⊗⋯⊗H(Ωd)H(\Omega;[0,T])\cong H([0,T])\otimes H(\Omega_1)\otimes\cdots\otimes H(\Omega_d) and represent the solution of (1) as

f(x,t)≈∑i1=1n1⋯∑id=1ndfi1…id(t)ϕi1(x1)⋯ϕid(xd),(3)f(\boldsymbol{x},t)\approx\sum_{i_1=1}^{n_1}\cdots\sum_{i_d=1}^{n_d}f_{i_1\ldots i_d}(t)\phi_{i_1}(x_1)\cdots\phi_{i_d}(x_d), \tag*{(3)}

where ϕij(xj)\phi_{i_j}(x_j) are one-dimensional orthonormal basis functions of H(Ωi)H(\Omega_i). Substituting (3) into (1) and projecting onto an appropriate finite-dimensional subspace of H(Ω)H(\Omega) yields the semi-discrete form

dfdt=G(f),f(0)=f0(4)\frac{d\boldsymbol{f}}{dt}=\boldsymbol{G}(\boldsymbol{f}), \qquad\boldsymbol{f}(0)=\boldsymbol{f}_0 \tag*{(4)}

Preprint submitted to ArXiv

where f:[0,T]→Rn1×n2×⋯×ndf : [0,T] \to\mathbb{R}^{n_1 \times n_2 \times\cdots\times n_d} is a multivariate array with coefficients fi1⋯id(t)f_{i_1 \cdots i_d}(t), and GG is the finite-dimensional representation of the nonlinear operator N\mathcal{N}. The number of degrees of freedom associated with the solution to the Cauchy problem (4) is Ndof=n1n2⋯ndN_{\mathrm{dof}} = n_1 n_2 \cdots n_d at each time t≥0t \ge0, which can be extremely large even for moderately small dimension dd. For instance, the solution of the Boltzmann-BGK equation on a six-dimensional (d=6d = 6) flat torus [9, 18, 34] with ni=128n_i = 128 basis functions in each position and momentum variable yields Ndof=1286=4398046511104N_{\mathrm{dof}} = 128^6 = 4398046511104 degrees of freedom at each time tt. This requires approximately 35.18 Terabytes per temporal snapshot if we store the solution tensor ff in a double precision IEEE 754 floating point format. Several general-purpose algorithms have been developed to mitigate such an exponential growth of degrees of freedom, the computational cost, and the memory requirements. These algorithms include, e.g., sparse collocation methods [6, 10, 23, 36], high-dimensional model representation (HDMR) [5, 11, 33], and techniques based on deep neural networks [12, 37, 38, 49].

In a parallel research effort that has its roots in quantum field theory and quantum entanglement, researchers have recently developed a new generation of algorithms based on tensor networks and low-rank tensor techniques to compute the solution of high-dimensional PDEs [4, 8, 13, 30, 31]. Tensor networks are essentially factorizations of entangled objects such as multivariate functions or operators, into networks of simpler objects which are amenable to efficient representation and computation. The process of building a tensor network relies on a hierarchical decomposition that can be visualized in terms of trees, and has its roots in the spectral theory for linear operators. Such rigorous mathematical foundations can be leveraged to construct high-order methods to compute the numerical solution of high-dimensional Cauchy problems of the form (4) at a cost that scales linearly with respect to the dimension dd, and polynomially with respect to the tensor rank.

In particular, a new class of algorithms to integrate (4) on a low-rank tensor manifold was recently proposed in [15, 16, 31, 40, 41, 47]. These algorithms are known as explicit step-truncation methods and they are based on integrating the solution f(t)f(t) off the tensor manifold for a short time using any conventional explicit time-stepping scheme, and then mapping it back onto the manifold using a tensor truncation operation (see Figure 2). To briefly describe these methods, let us discretize the ODE (4) in time with a one-step method on an evenly-spaced temporal grid as

Sketch of implicit and explicit step-truncation integration methods

Figure 2. Sketch of implicit and explicit step-truncation integration methods. Given a tensor fkf_k with multilinear rank rr on the tensor manifold Hr\mathcal{H}_r, we first perform an explicit time-step, e.g., with the conventional time-stepping scheme (5). The explicit step-truncation integrator then projects ΨΔt(G,fk)\Psi_{\Delta t}(G,f_k) onto a new tensor manifold Hs\mathcal{H}_s (solid red line). The multilinear rank ss is chosen adaptively based on desired accuracy and stability constraints [40]. On the other hand, the implicit step-truncation method takes ΨΔt(G,fk)\Psi_{\Delta t}(G,f_k) as input and generates a sequence of fixed-point iterates f[j]f^{[j]} shown as dots connected with blue lines. The last iterate is then projected onto a low rank tensor manifold, illustrated here also as a red line landing on Hs\mathcal{H}_s. This operation is equivalent to the compression step in the HT/TT-GMRES algorithm described in [20].

fk+1=ΨΔt(G,fk),f0=f(0),(5)\mathbf{f}_{k+1} = \boldsymbol{\Psi}_{\Delta t}(G,\mathbf{f}_k), \qquad\mathbf{f}_0 = f(0), \tag*{(5)}

where fk\mathbf{f}_k denotes an approximation of f(kΔt)f(k\Delta t) for k=0,1,…k = 0,1,\ldots, and ΨΔt\boldsymbol{\Psi}_{\Delta t} is an increment function. To obtain a step-truncation integrator, we simply apply a truncation operator Tr(⋅)\mathcal{T}_r(\cdot), i.e., a nonlinear projection onto a tensor manifold Hr\mathcal{H}_r with multilinear rank rr [46] to the scheme (5). This yields

fk+1=Tr(ΨΔt(G,fk)).(6)\mathbf{f}_{k+1} = \mathcal{T}_r\left(\boldsymbol{\Psi}_{\Delta t}(G,\mathbf{f}_k)\right). \tag*{(6)}

The need for tensor rank-reduction when iterating (5) can be easily understood by noting that tensor operations such as the application of an operator to a tensor and the addition between two tensors naturally increase tensor rank [32]. Hence, iterating (6) with no rank reduction can yield a fast increase in tensor rank, which, in turn, can tax computational resources heavily.

Explicit step-truncation algorithms of the form (6) were studied extensively in [31, 40]. In particular, error estimates and convergence results were obtained for both fixed-rank and rank-adaptive integrators, i.e., integrators in which the tensor rank rr is selected at each time step based on accuracy and stability constraints. Step-truncation methods are very simple to implement as they rely only on arithmetic operations between tensors, which can be performed by scalable parallel algorithms [3, 14, 25, 43].

While explicit step-truncation methods have proven successful in integrating a wide variety of high-dimensional initial value problems, their effectiveness for stiff problems is limited. Indeed, the combination of non-linearity and stiffness may introduce time-step restrictions which could make explicit step-truncation integration computationally infeasible. As an example, in Figure 1 we show that the explicit step-truncation midpoint method applied to the Allen-Cahn equation

Explicit and implicit step-truncation midpoint methods

Figure 1. Explicit and implicit step-truncation midpoint methods applied the Allen-Cahn equation (7) with ε=0.1\varepsilon= 0.1. It is seen that the explicit step-truncation midpoint method undergoes a numerical instability for Δt=10−3\Delta t = 10^{-3} while the implicit step-truncation midpoint method retains accuracy and stability for Δt=10−3\Delta t = 10^{-3}, and even larger time steps. Stability implicit step-truncation midpoint is studied in section 4.

∂f∂t=εΔf+f−f3,(7)\frac{\partial f}{\partial t} = \varepsilon\Delta f + f - f^3, \tag*{(7)}

undergoes a numerical instability for Δt=10−3\Delta t = 10^{-3}.

The main objective of this paper is to develop a new class of rank-adaptive implicit step-truncation algorithms to integrate high-dimensional initial value problems of the form (4) on low-rank tensor manifolds. The main idea of these new integrators is illustrated in Figure 2. Roughly speaking, implicit step-truncation method take fk∈Hrf_k \in\mathcal{H}_r (Hr\mathcal{H}_r is a HT or TT tensor manifold with multilinear rank rr) and ΨΔt(G,fk)\Psi_{\Delta t}(G,f_k) as input and generate a sequence of inexact Newton iterates f[j]f^{[j]} converging to a point tensor manifold Hs\mathcal{H}_s. Once f[j]f^{[j]} is sufficiently close to Hs\mathcal{H}_s we project it onto the manifold via a standard truncation operation. This operation is also known as “compression step” in the HT/TT-GMRES algorithm described in [20]. Of course the computational cost of implicit step-truncation methods is higher than that of explicit step truncation methods for one single step. However, implicit methods allow to integrate stably with larger time-steps while retaining accuracy. Previous research on implicit tensor integration leveraged the Alternating Least Squares (ALS) algorithm [8, 13, 19], which essentially attempts to solve an optimization problem on a low-rank tensor manifold to compute the solution of (4) at each time step. As is well-known, ALS is equivalent to the (linear) block Gauss-Seidel iteration applied to the Hessian matrix of the residual, and can have convergence issues [45].

The paper is organized as follows. In section 1, we briefly review rank-adaptive explicit step-truncation methods, and present a new convergence proof for these methods which applies also to implicit step-truncation methods. In section 2, we discuss the proposed new algorithms for implicit step-truncation integration. In section 3 we study convergence of particular implicit step-truncation methods, namely the step-truncation implicit Euler and midpoint methods. In section 4 we prove that the stability region of an implicit step-truncation method is identical to that of the implicit method without tensor truncation. Finally, in section 5 we present numerical applications of implicit step-truncation algorithms to stiff PDEs. In particular, we study a two-dimensional Allen-Cahn equation, a four-dimensional Fokker-Planck equation, and a six-dimensional nonlinear Schrödinger equation. We also include a brief appendix in which we discuss numerical algorithms to solve linear and nonlinear algebraic equations on tensor manifolds via the inexact Newton’s method with HT/TT-GMRES iterations.

Explicit step-truncation methods

In this section we briefly review explicit step-truncation methods to integrate the tensor-valued ODE (4) on tensor manifolds with variable rank. For a complete account of this theory see [40]. We begin by first discretizing the ODE in time with any standard explicit one-step method on an evenly-spaced temporal grid

fk+1=ΨΔt(G,fk).(8)f_{k+1} = \Psi_{\Delta t}(G,f_k). \tag*{(8)}

Here, fkf_k denotes an approximation of the exact solution f(kΔt)f(k\Delta t) for k=1,2,…,Nk = 1, 2, \ldots, N, and ΨΔt\Psi_{\Delta t} is an increment function. For example, ΨΔt\Psi_{\Delta t} can be the increment function corresponding to the Euler forward method

ΨΔt(G,fk)=fk+ΔtG(fk).(9)\Psi_{\Delta t}(G,f_k) = f_k + \Delta t G(f_k). \tag*{(9)}

In the interest of saving computational resources when iterating (8) we look for an approximation of fkf_k on a low-rank tensor manifold Hr\mathcal{H}_r [46] with multilinear rank rr. Hr\mathcal{H}_r is taken to be the manifold of Hierarchical Tucker (HT) tensors. The easiest way for approximating (8) on Hr\mathcal{H}_r is to apply a nonlinear projection operator [24] (truncation operator)

Tr:Rn1×n2×⋯×nd→H‾r,(10)\mathcal{T}_r : \mathbb{R}^{n_1 \times n_2 \times\cdots\times n_d} \to\overline{\mathcal{H}}_r, \tag*{(10)}

where H‾r\overline{\mathcal{H}}_r denotes the closure of Hr\mathcal{H}_r. This yields the explicit step-truncation scheme

fk+1=Tr(ΨΔt(G,fk)).(11)f_{k+1} = \mathcal{T}_r\left(\Psi_{\Delta t}(G,f_k)\right). \tag*{(11)}

The rank rr can vary with the time step based on appropriate error estimates as time integration proceeds [40]. We can also project G(f)G(f) onto H‾r\overline{\mathcal{H}}_r before applying ΨΔt\Psi_{\Delta t}. With reference to (9) this yields

fk+1=Tr2(fk+ΔtTr1(G(fk))).(12)f_{k+1} = \mathcal{T}_{r_2}\left(f_k + \Delta t\mathcal{T}_{r_1}\left(G(f_k)\right)\right). \tag*{(12)}

Here r1r_1 and r2r_2 are truncation ranks determined by the inequalities2

∥G(fk)−Tr1(G(fk))∥≤e1,∥f~k+1−Tr2(f~k+1)∥≤e2,(13)\lVert G(f_k) - \mathcal{T}_{r_1}(G(f_k)) \rVert\le e_1,\qquad \lVert\widetilde{f}_{k+1} - \mathcal{T}_{r_2}\left(\widetilde{f}_{k+1}\right) \rVert\le e_2, \tag*{(13)}

where e1e_1 and e2e_2 are chosen error thresholds. As before, r1r_1 and r2r_2 can change with every time step. In particular, if we choose e1=K1Δte_1 = K_1\Delta t and e2=K2Δt2e_2 = K_2\Delta t^2 (with K1K_1 and K2K_2 given constants) then the step-truncation method (12) is convergent (see [40] for details). More generally, let

fk+1=ΦΔt(G,fk,e)(14)f_{k+1} = \Phi_{\Delta t}(G,f_k,e) \tag*{(14)}

be an explicit step-truncation method in which all we project all G(fk)G(f_k) appearing in the increment function ΨΔt(G,fk)\Psi_{\Delta t}(G,f_k) onto tensor manifolds H‾ri\overline{\mathcal{H}}_{r_i} by setting suitable error thresholds e=(e1,e2,…)e = (e_1,e_2,\ldots). For instance, if ΨΔt\Psi_{\Delta t} is defined by the explicit midpoint method, i.e.,

ΨΔt(G,fk)=fk+G(fk+Δt2G(fk))(15)\Psi_{\Delta t}(G,f_k)=f_k+G\left(f_k+\frac{\Delta t}{2}G(f_k)\right) \tag*{(15)}

then

ΦΔt(G,fk,e)=Tr3(fk+Tr2[G(fk+Δt2Tr1[G(fk)])])(16)\Phi_{\Delta t}(G,f_k,e)=\mathcal{T}_{r_3}\left(f_k+\mathcal{T}_{r_2}\left[G\left(f_k+\frac{\Delta t}{2}\mathcal{T}_{r_1}[G(f_k)]\right)\right]\right) \tag*{(16)}

where e=(e1,e2,e3)e=(e_1,e_2,e_3) is a vector collecting the truncation error thresholds yielding the multilinear ranks r1r_1, r2r_2 and r3r_3. By construction, step-truncation methods of the form (14) satisfy

∥ΨΔt(G,f)−ΦΔt(G,f,e)∥≤R(e),(17)\left\lVert\Psi_{\Delta t}(G,f)-\Phi_{\Delta t}(G,f,e)\right\rVert\leq R(e), \tag*{(17)}

where R(e)R(e) is the error due to tensor truncation. We close this section with a reformulation of the convergence theorem for explicit step-truncation methods in [40], which applies also to implicit methods.

Theorem 1 (Convergence of step-truncation methods). Let φΔt(G,f)\varphi_{\Delta t}(G,f) be the one-step exact flow map defined by (4), and ΦΔt(G,f,e)\Phi_{\Delta t}(G,f,e) be the increment function of a step-truncation method with local error of order pp, i.e.,

∥φΔt(G,f)−ΦΔt(G,f,e)∥≤KΔtp+1as Δt→0.(18)\left\lVert\varphi_{\Delta t}(G,f)-\Phi_{\Delta t}(G,f,e)\right\rVert\leq K\Delta t^{p+1}\quad\text{as }\Delta t\to0. \tag*{(18)}

If there exist truncation errors e=e(Δt)e=e(\Delta t) (function of Δt\Delta t) and constants C,E>0C,E>0 (dependent on GG) so that the stability condition

∥ΦΔt(G,f^,e)−ΦΔt(G,f~,e)∥≤(1+CΔt)∥f^−f~∥+EΔtm+1(19)\left\lVert\Phi_{\Delta t}(G,\hat{f},e)-\Phi_{\Delta t}(G,\tilde{f},e)\right\rVert\leq(1+C\Delta t)\left\lVert\hat{f}-\tilde{f}\right\rVert+E\Delta t^{m+1} \tag*{(19)}

holds as Δt→0\Delta t\to0, then the step-truncation method is convergent with order z=min⁡(m,p)z=\min(m,p).

Proof. Under the assumption that Δt\Delta t is small enough for our stability and consistency to hold, we proceed by induction on the number of steps. The one-step case coincides with the consistency condition. Next, we assume that

∥φΔt(N−1)(G,f0)−fN−1∥≤QN−1Δtz.(20)\left\lVert\varphi_{\Delta t(N-1)}(G,f_0)-f_{N-1}\right\rVert\leq Q_{N-1}\Delta t^z. \tag*{(20)}

Let T=NΔtT=N\Delta t be the final integration time. By applying triangle inequality and the semigroup property of the flow map,

∥φT(G,f0)−ΦΔt(G,fN−1,e)∥≤∥φΔt(G,φΔt(N−1)(G,f0))−ΦΔt(G,φΔt(N−1)(G,f0),e)∥+∥ΦΔt(G,φΔt(N−1)(G,f0),e)−ΦΔt(G,fN−1,e)∥.(21)\begin{aligned} \left\lVert\varphi_T(G,f_0)-\Phi_{\Delta t}(G,f_{N-1},e)\right\rVert &\leq\left\lVert\varphi_{\Delta t}\left(G,\varphi_{\Delta t(N-1)}(G,f_0)\right)-\Phi_{\Delta t}\left(G,\varphi_{\Delta t(N-1)}(G,f_0),e\right)\right\rVert\\ &\quad+\left\lVert\Phi_{\Delta t}\left(G,\varphi_{\Delta t(N-1)}(G,f_0),e\right)-\Phi_{\Delta t}(G,f_{N-1},e)\right\rVert. \tag*{(21)} \end{aligned}

Using the consistency condition (18) we can bound the first term at the right hand side of (21) by KN−1Δtp+1K_{N-1}\Delta t^{p+1}, where KN−1K_{N-1} represents a local error coefficient. On the other hand, using the stability condition (19) we can bound the second term at the right hand side of (21) as

∥ΦΔt(G,φΔt(N−1)(G,f0),e)−ΦΔt(G,fN−1,e)∥≤(1+CΔt)∥φΔt(N−1)(G,f0)−fN−1∥+EΔtm+1.(22)\left\lVert\Phi_{\Delta t}\left(G,\varphi_{\Delta t(N-1)}(G,f_0),e\right)-\Phi_{\Delta t}(G,f_{N-1},e)\right\rVert\leq(1+C\Delta t)\left\lVert\varphi_{\Delta t(N-1)}(G,f_0)-f_{N-1}\right\rVert+E\Delta t^{m+1}. \tag*{(22)}

A substitution of (22) and (20) into (21) yields

∥φT(G,f0)−ΦΔt(G,fN−1,e)∥≤KN−1Δtp+1+(1+CΔt)QN−1Δtz+EΔtm+1.\left\lVert\varphi_T(G,f_0)-\Phi_{\Delta t}(G,f_{N-1},e)\right\rVert\leq K_{N-1}\Delta t^{p+1}+(1+C\Delta t)Q_{N-1}\Delta t^z+E\Delta t^{m+1}.

Recalling that z=min⁡(m,p)z=\min(m,p) completes the proof.

We remark that the above proof may be modified to include explicit step-truncation linear multi-step methods, i.e., step-truncation Adams methods. To this end, it is sufficient to replace fkf_k with the vector (fk−s,fk−s+1,…,fk)(f_{k-s},f_{k-s+1},\ldots,f_k) and the stability condition (19) with

∥ΦΔt(G,f^1,f^2,…,f^s,e)−ΦΔt(G,f~1,f~2,…,f~s,e)∥≤∥f^s−f~s∥+∑j=1sCjΔt∥f^j−f~j∥+EΔtm+1.(23)\left\lVert\Phi_{\Delta t}(G,\hat{f}_1,\hat{f}_2,\ldots,\hat{f}_s,e)-\Phi_{\Delta t}(G,\tilde{f}_1,\tilde{f}_2,\ldots,\tilde{f}_s,e)\right\rVert\leq\left\lVert\hat{f}_s-\tilde{f}_s\right\rVert+\sum_{j=1}^{s}C_j\Delta t\left\lVert\hat{f}_j-\tilde{f}_j\right\rVert+E\Delta t^{m+1}. \tag*{(23)}

We then have an analogous theorem proven using an inductive argument based on the initial conditions f(0),f(Δt),…,f((s−1)Δt)f(0),f(\Delta t),\ldots,f((s-1)\Delta t).

Implicit step-truncation methods

To introduce implicit step-truncation tensor methods, let us begin with the standard Euler backward scheme

fk+1=fk+ΔtG(fk+1),(24)\mathbf{f}_{k+1}=\mathbf{f}_k+\Delta t\mathbf{G}(\mathbf{f}_{k+1}), \tag*{(24)}

and the associated root-finding problem

Hk(fk+1)=fk+1−fk−ΔtG(fk+1)=0.(25)\mathbf{H}_k(\mathbf{f}_{k+1})=\mathbf{f}_{k+1}-\mathbf{f}_k-\Delta t\mathbf{G}(\mathbf{f}_{k+1})=0. \tag*{(25)}

Equation (25) allows us to compute fk+1\mathbf{f}_{k+1} as a zero of the function Hk\mathbf{H}_k. This can be done, e.g., using the Newton’s method with initial guess fk+1[0]=fk\mathbf{f}_{k+1}^{[0]}=\mathbf{f}_k. As is well-known, if the Jacobian of Hk\mathbf{H}_k is invertible within a neighborhood of fk\mathbf{f}_k, then the implicit function theorem guarantees the existence of a locally differentiable (in some neighborhood of fk\mathbf{f}_k) nonlinear map ΘΔt\mathbf{\Theta}_{\Delta t} depending on G\mathbf{G} such that

fk+1=ΘΔt(G,fk).(26)\mathbf{f}_{k+1}=\mathbf{\Theta}_{\Delta t}(\mathbf{G},\mathbf{f}_k). \tag*{(26)}

In the setting of Newton’s method described above, the map ΘΔt\mathbf{\Theta}_{\Delta t} is computed iteratively. An implicit step-truncation scheme can be then formulated by applying the tensor truncation operator Tr\mathcal{T}_r to the right hand side of (26), i.e.,

fk+1=Tr(ΘΔt(G,fk)).(27)\mathbf{f}_{k+1}=\mathcal{T}_r\left(\mathbf{\Theta}_{\Delta t}(\mathbf{G},\mathbf{f}_k)\right). \tag*{(27)}

The tensor truncation rank rr can be selected based on the inequality

∥Tr(ΘΔt(G,fk))−ΘΔt(G,fk)∥≤AΔt2.(28)\left\|\mathcal{T}_r\left(\mathbf{\Theta}_{\Delta t}(\mathbf{G},\mathbf{f}_k)\right)-\mathbf{\Theta}_{\Delta t}(\mathbf{G},\mathbf{f}_k)\right\|\le A\Delta t^2. \tag*{(28)}

It was shown in [40] that this yields an order one (in time) integration scheme. Of course, if the Jacobian of Hk\mathbf{H}_k in equation (25) can be computed and stored in computer memory, then we can approximate fk+1=ΘΔt(G,fk)\mathbf{f}_{k+1}=\mathbf{\Theta}_{\Delta t}(\mathbf{G},\mathbf{f}_k) for any given fk\mathbf{f}_k and G\mathbf{G} using Newton’s iterations. However, the exact Newton’s method is not available to us in the high-dimensional tensor setting.

Hence, we look for an approximation of ΘΔt(G,fk)\mathbf{\Theta}_{\Delta t}(\mathbf{G},\mathbf{f}_k) computed using the inexact Newton method [17]. For the inexact matrix inverse step, we apply the relaxed TT-GMRES algorithm described in [20]. This is an iterative method for the solution of linear equations which makes use of an inexact matrix-vector product defined by low-rank truncation. Though the algorithm was developed for TT tensors, it may be also applied to HT tensors without significant changes.

In Appendix Appendix § 7 we describe the inexact Newton’s method with HT/TT-GMRES iterations to solve an arbitrary algebraic equation of the form Hk(f)=0\mathbf{H}_k(\mathbf{f})=0 (e.g., equation (25)) on a tensor manifold with a given rank. The algorithm can be used to approximate the mapping ΘΔt(G,fk)\mathbf{\Theta}_{\Delta t}(\mathbf{G},\mathbf{f}_k) corresponding to any implicit integrator, and it returns a tensor with can be then truncated further as in (27). This operation is equivalent to the so-called “compression step” in [20] and it is described in detail in the next section.

The compression step

While increasing the tensor rank may be necessary for convergence of the HT/TT-GMRES iterations, it is possible that we raise the rank by more than is required for the desired order of accuracy in a single time step. Therefore, it is convenient to apply an additional tensor truncation after computing, say, jj steps of the HT inexact Newton’s method which returns fk+1[j]\mathbf{f}_{k+1}^{[j]}. This is the same as the “compression step” at the end of HT/TT-GMRES algorithm as presented in [20]. This gives us our final estimate of f((k+1)Δt)\mathbf{f}((k+1)\Delta t) as

fk+1=Tr(fk+1[j]),∥Tr(fk+1[j])−fk+1[j]∥≤er.(29)\mathbf{f}_{k+1}=\mathcal{T}_r\left(\mathbf{f}_{k+1}^{[j]}\right),\qquad\left\|\mathcal{T}_r\left(\mathbf{f}_{k+1}^{[j]}\right)-\mathbf{f}_{k+1}^{[j]}\right\|\le e_r. \tag*{(29)}

Regarding the selection of the truncation error ere_r we proceed as follows. Suppose that ΨΔt(G,fk)\mathbf{\Psi}_{\Delta t}(\mathbf{G},\mathbf{f}_k) is an explicit integration scheme of the same order (or higher) than the implicit scheme being considered. Then we can estimate local error as

∥fk+1[j]−f((k+1)Δt)∥≤∥fk+1[j]−ΨΔt(G,fk)∥+∥ΨΔt(G,fk)−f((k+1)Δt)∥=∥fk+1[j]−ΨΔt(G,fk)∥+O(Δtp+1),(30)\begin{aligned} \left\|\mathbf{f}_{k+1}^{[j]}-\mathbf{f}((k+1)\Delta t)\right\|\le\left\|\mathbf{f}_{k+1}^{[j]}-\mathbf{\Psi}_{\Delta t}(\mathbf{G},\mathbf{f}_k)\right\|+\left\|\mathbf{\Psi}_{\Delta t}(\mathbf{G},\mathbf{f}_k)-\mathbf{f}((k+1)\Delta t)\right\| \\ &=\left\|\mathbf{f}_{k+1}^{[j]}-\mathbf{\Psi}_{\Delta t}(\mathbf{G},\mathbf{f}_k)\right\|+O(\Delta t^{p+1}), \tag*{(30)} \end{aligned}

Thus, we may roughly estimate the local truncation error and set this as the chosen error for approximation to HT or TT rank rr using

er=∥fk+1[j]−ΨΔt(G,fk)∥.(31)e_r = \left\|f_{k+1}^{[j]}-\Psi_{\Delta t}(G,f_k)\right\|. \tag*{(31)}

We may drop more singular values than needed, especially if the choice of Δt\Delta t is outside the region of stability of the explicit scheme ΨΔt(G,fk)\Psi_{\Delta t}(G,f_k). However, this estimate guarantees that we do not change the overall convergence rate. Moreover, it cannot impact stability of the implicit step-truncation integrator since the compression step has operator norm equal to one, regardless of the rank chosen. This statement is supported by the analysis presented in [41] for step-truncation linear multi-step methods. In all our numerical experiments we use the explicit step-truncation midpoint method to estimate local error, i.e., ΨΔt(G,fk)\Psi_{\Delta t}(G,f_k) in (31) is set as in (15).

Convergence analysis of implicit step-truncation methods

In this section we show that applying the inexact Newton iterations with HT/TT-GMRES to the implicit Euler and the implicit midpoint methods result in implicit step-truncation schemes that fit into the framework of Theorem 1, and therefore are convergent.

Implicit step-truncation Euler method

Consider the implicit Euler scheme (25), and suppose that the solution of the nonlinear equation Hk(fk+1)=0H_k(f_{k+1})=0 is computed using the inexact Newton method with HT/TT-GMRES iterations as discussed in Appendix § 7. Let fk+1[j]f_{k+1}^{[j]} (j=1,2,…j=1,2,\ldots) be the sequence of tensors generated by the algorithm and approximating fk+1f_{k+1} (exact solution of Hk(fk+1)=0H_k(f_{k+1})=0). We set a stopping criterion for terminating Newton’s iterations based on the residual, i.e.,

∥Hk(fk+1[j])∥≤εtol.(32)\left\|H_k\left(f_{k+1}^{[j]}\right)\right\|\leq\varepsilon_{\mathrm{tol}}. \tag*{(32)}

This allows us to adjust the rank of fk+1[j]f_{k+1}^{[j]} from one time step to the next, depending on the desired accuracy εtol\varepsilon_{\mathrm{tol}}. Our goal is to analyze convergence of such rank-adaptive implicit method when a finite number of contraction mapping steps is taken. To this end, we will fit the method into the framework of Theorem 1. We begin by noticing that

∥fk+1−fk+1[j]∥=∥Hk−1(Hk(fk+1))−Hk−1(Hk(fk+1[j]))∥≤LHk−1∥Hk(fk+1[j])∥≤LHk−1εtol,(33)\left\|f_{k+1}-f_{k+1}^{[j]}\right\|=\left\|H_k^{-1}\left(H_k(f_{k+1})\right)-H_k^{-1}\left(H_k\left(f_{k+1}^{[j]}\right)\right)\right\|\leq L_{H_k^{-1}}\left\|H_k\left(f_{k+1}^{[j]}\right)\right\|\leq L_{H_k^{-1}}\varepsilon_{\mathrm{tol}}, \tag*{(33)}

where LHk−1L_{H_k^{-1}} is the local Lipschitz constant of the smooth inverse map Hk−1H_k^{-1}, the existence of which is granted by the inverse function theorem. This allows us to write the local truncation error as

∥f(Δt)−fk+1[j]∥≤∥f(Δt)−f1∥+∥f1−fk+1[j]∥≤K1Δt2+LHk−1εtol,(34)\left\|f(\Delta t)-f_{k+1}^{[j]}\right\|\leq\left\|f(\Delta t)-f_1\right\|+\left\|f_1-f_{k+1}^{[j]}\right\|\leq K_1\Delta t^2+L_{H_k^{-1}}\varepsilon_{\mathrm{tol}}, \tag*{(34)}

where K1K_1 is a local error coefficient. In order to maintain order one convergence, we require that εtol≤KΔt2\varepsilon_{\mathrm{tol}}\leq K\Delta t^2 for some constant K≥0K\geq0.

Next, we discuss the stability condition (19) in the context of the implicit step-truncation Euler scheme, assuming that fk+1f_{k+1} can be found exactly by the inexact Newton’s method, eventually after an infinite number of iterations. Denote by f^0\widehat{f}_0, f~0\widetilde{f}_0 two different initial conditions. Performing one step of the standard implicit Euler’s method yields the following bound

∥f^1−f~1∥=∥(f^0+ΔtG(f^1))−(f~0+ΔtG(f~1))∥≤∥f^0−f~0∥+ΔtLG∥f^1−f~1∥.\left\|\widehat{f}_1-\widetilde{f}_1\right\|=\left\|\left(\widehat{f}_0+\Delta tG(\widehat{f}_1)\right)-\left(\widetilde{f}_0+\Delta tG(\widetilde{f}_1)\right)\right\|\leq\left\|\widehat{f}_0-\widetilde{f}_0\right\|+\Delta tL_G\left\|\widehat{f}_1-\widetilde{f}_1\right\|.

where LGL_G is the Lipschitz constant of GG. By collecting like terms, we obtain

∥f^1−f~1∥≤11−ΔtLG∥f^0−f~0∥≤(1+2ΔtLG)∥f^0−f~0∥.(35)\left\|\widehat{f}_1-\widetilde{f}_1\right\|\leq\frac{1}{1-\Delta tL_G}\left\|\widehat{f}_0-\widetilde{f}_0\right\|\leq(1+2\Delta tL_G)\left\|\widehat{f}_0-\widetilde{f}_0\right\|. \tag*{(35)}

The last inequality comes by noting that 1/(1−ΔtLG)≤1+2ΔtLG1/(1-\Delta tL_G)\leq1+2\Delta tL_G when Δt\Delta t is sufficiently small, i.e., Δt≤1/(2LG)\Delta t\leq1/(2L_G). This is zero-stability condition, i.e., a stability condition that holds for small Δt\Delta t, which will be used for convergence analysis. Regarding the behavior of the scheme for finite Δt\Delta t we will show in section 4 that the implicit step-truncation Euler scheme is unconditionally stable. Next, we derive a stability condition of the form (35) when the root of Hk(fk+1)=0H_k(f_{k+1})=0 is computed with the inexact Newton’s method with HT/TT-GMRES iterations. In this case we have

∥f^1[j]−f~1[m]∥≤∥f^1[j]−f^1[∞]∥+∥f^1[∞]−f~1[∞]∥+∥f~1[∞]−f~1[m]∥=∥f^1[j]−f^1∥+∥f^1−f~1∥+∥f~1[m]−f~1∥≤(1+2LGΔt)∥f^0−f~0∥+2LHk−1εtol.(36)\begin{aligned} \left\|\widehat{f}_1^{[j]}-\widetilde{f}_1^{[m]}\right\| &\leq\left\|\widehat{f}_1^{[j]}-\widehat{f}_1^{[\infty]}\right\|+\left\|\widehat{f}_1^{[\infty]}-\widetilde{f}_1^{[\infty]}\right\|+\left\|\widetilde{f}_1^{[\infty]}-\widetilde{f}_1^{[m]}\right\| \\ &= \left\|\widehat{f}_1^{[j]}-\widehat{f}_1\right\|+\left\|\widehat{f}_1-\widetilde{f}_1\right\|+\left\|\widetilde{f}_1^{[m]}-\widetilde{f}_1\right\| \\ &\leq(1+2L_G\Delta t)\left\|\widehat{f}_0-\widetilde{f}_0\right\|+2L_{H_k}^{-1}\varepsilon_{\mathrm{tol}}. \tag*{(36)} \end{aligned}

Thus, the stability condition is satisfied by the same condition on εtol\varepsilon_{\mathrm{tol}} that satisfies the first-order consistency condition (34), i.e., εtol≤KΔt2\varepsilon_{\mathrm{tol}}\leq K\Delta t^2. At this point we apply Theorem 1 with consistency and stability conditions (18)–(19) replaced by (34) and (36), respectively, and conclude that the implicit step-truncation Euler scheme is convergent with order one if εtol≤KΔt2\varepsilon_{\mathrm{tol}}\leq K\Delta t^2.

Remark 1. When GG is linear, i.e., when the tensor ODE (4) is linear, then we may apply HT/TT-GMRES algorithm in Appendix Appendix § 7 without invoking Newton’s method. In this case, the local error coefficient LHk−1L_{H_k}^{-1} can be exchanged for the coefficient of ε\varepsilon at the right side of inequality (A.6).

Implicit step-truncation midpoint method

The implicit midpoint rule [26],

fk+1=fk+ΔtG(12(fk+fk+1)),(37)f_{k+1}=f_k+\Delta tG\left(\frac{1}{2}(f_k+f_{k+1})\right), \tag*{(37)}

is a symmetric and symplectic method of order 2. By introducing

Hk(fk+1)=fk+1−fk−ΔtG(12(fk+fk+1))=0(38)H_k(f_{k+1})=f_{k+1}-f_k-\Delta tG\left(\frac{1}{2}(f_k+f_{k+1})\right)=0 \tag*{(38)}

we again see the implicit method as a root finding problem at each time step. To prove convergence of the implicit step-truncation midpoint method we follow the same steps described in the previous section. To this end, consider the sequence of tensors fk+1[j]f_{k+1}^{[j]} generated by the inexact Newton method with HT/TT-GMRES iterations (see Appendix Appendix § 7) applied to (38). The sequence of tensors fk+1[j]f_{k+1}^{[j]} approximates fk+1f_{k+1} satisfying (38). As before, we terminate the inexact Newton’s iterations as soon as condition (32) is satisfied. By repeating the same steps that led us to inequality (33), we have

∥f(Δt)−f1[j]∥≤K1Δt3+LHk−1εtol.(39)\left\|f(\Delta t)-f_1^{[j]}\right\|\leq K_1\Delta t^3+L_{H_k}^{-1}\varepsilon_{\mathrm{tol}}. \tag*{(39)}

Hence, setting the stopping tolerance as εtol≤KΔt3\varepsilon_{\mathrm{tol}}\leq K\Delta t^3 we get second-order consistency. We use this to determine the stability condition (19). As before, we derive the condition for when the zero of (38) is exact. Denote by f^0\widehat{f}_0, f~0\widetilde{f}_0 two different initial conditions. Performing one step of the standard implicit midpoint method yields the following bound

∥f^1−f~1∥≤(1+ΔtLG2)∥f^0−f~0∥+ΔtLG2∥f^1−f~1∥.\left\|\widehat{f}_1-\widetilde{f}_1\right\|\leq\left(1+\Delta t\frac{L_G}{2}\right)\left\|\widehat{f}_0-\widetilde{f}_0\right\|+\Delta t\frac{L_G}{2}\left\|\widehat{f}_1-\widetilde{f}_1\right\|.

By collecting like terms we see that when Δt≤1/LG\Delta t\leq1/L_G,

∥f^1−f~1∥≤2+ΔtLG2−ΔtLG∥f^0−f~0∥≤(1+Δt3LG2)∥f^0−f~0∥.(40)\begin{aligned} \left\|\widehat{f}_1-\widetilde{f}_1\right\|&\leq\frac{2+\Delta tL_G}{2-\Delta tL_G}\left\|\widehat{f}_0-\widetilde{f}_0\right\|\\ &\leq\left(1+\Delta t\frac{3L_G}{2}\right)\left\|\widehat{f}_0-\widetilde{f}_0\right\|. \tag*{(40)} \end{aligned}

The zero-stability condition for the implicit step-truncation midpoint method can now be found by repeating the arguments of inequality (36). This gives

∥f^1[j]−f~1[m]∥≤(1+LGΔt)∥f^0−f~0∥+2LHκk−1εtol.(41)\left\| \widehat{f}_1^{[j]}-\widetilde{f}_1^{[m]} \right\| \leq(1+L_G\Delta t)\left\| \widehat{f}_0-\widetilde{f}_0 \right\|+2L_H\kappa^{-1}_{k}\varepsilon_{\mathrm{tol}}. \tag*{(41)}

Thus, the stability condition is satisfied by the same condition on εtol\varepsilon_{\mathrm{tol}} that satisfies the second-order consistency condition (39), i.e., εtol≤KΔt3\varepsilon_{\mathrm{tol}}\leq K\Delta t^3. At this point we apply Theorem 1 with consistency and stability conditions (18)–(19) replaced by (39) and (41), respectively, and conclude that the implicit step-truncation midpoint scheme is convergent with order two if εtol≤KΔt3\varepsilon_{\mathrm{tol}}\leq K\Delta t^3.

Stability analysis

We now address absolute stability of the proposed implicit step-truncation methods. This notion of stability is related to the behavior of the schemes when applied the initial value problem

dfdt=Lf,f(0)=f0(42)\frac{d f}{d t}=L f,\qquad f(0)=f_0 \tag*{(42)}

where LL is a linear operator with eigenvalues in in the left half complex plane. After applying any standard implicit time stepping scheme, we end up with a system of linear equations of the form

Afk+1=Wfk.(43)A f_{k+1}=W f_k. \tag*{(43)}

Specifically, for the implicit Euler we have A=I−ΔtLA=I-\Delta tL, W=IW=I while for the implicit midpoint method we have A=I−0.5ΔtLA=I-0.5\Delta tL, W=I+0.5ΔtLW=I+0.5\Delta tL. As is well known, both implicit Euler and Implicit midpoint are unconditionally stable, in the sense that for any Δt>0\Delta t>0, ∥fk∥→0\|f_k\|\to0 as k→∞k\to\infty. One way of proving this is by noting that whenever the eigenvalues of LL have negative real part, we get

∥A−1W∥<1,(44)\|A^{-1}W\|<1, \tag*{(44)}

and therefore the mapping A−1WA^{-1}W is contractive. This implies the sequence fkf_k defined by (43) converges to zero. The following theorem characterizes what happens when we exchange exact matrix inverse A−1A^{-1} with an inexact inverse computed by tensor HT/TT-GMRES iterations.

Theorem 2 (Absolute stability of implicit step-truncation methods). Consider an implicit time stepping scheme of the form (43), and suppose that ∥A−1W∥<1\|A^{-1}W\|<1. Denote by f^k\widehat{f}_k the solution of Af^k=Wf^k−1A\widehat{f}_k=W\widehat{f}_{k-1} (k=1,2,…k=1,2,\ldots) obtained with the HT/TT-GMRES tensor solver described in Appendix § 7, with mm Krylov iterations and stopping tolerance η\eta. If

∥Af^k−Wf^k−1∥≤m∥A∥∥A−1∥η,(45)\left\|A\widehat{f}_k-W\widehat{f}_{k-1}\right\|\leq m\|A\|\|A^{-1}\|\eta, \tag*{(45)}

then the distance between f^k\widehat{f}_k and the exact solution fk=A−1Wfk−1f_k=A^{-1}Wf_{k-1} can be bounded as

∥f^k−fk∥≤m∥A∥∥A−1∥21−∥A−1W∥η.(46)\left\|\widehat{f}_k-f_k\right\|\leq\frac{m\|A\|\|A^{-1}\|^2}{1-\|A^{-1}W\|}\eta. \tag*{(46)}

Note that (46) implies that ∥f^k∥=O(η)\|\widehat{f}_k\|=O(\eta) as k→∞k\to\infty. In the context of HT/TT-GMRES iterations, the number η\eta can be controlled by setting the stopping tolerance in Lemma 1 (Appendix § 7) as

εk=η∥Wf^k∥.(47)\varepsilon_k=\frac{\eta}{\|W\widehat{f}_k\|}. \tag*{(47)}

at each time step kk.

Proof. The proof follows from a straightforward inductive argument. For k=1k=1 we have

f^1−f1=A−1Af^1−A−1Wf0=A−1(Af^1−Wf0).(48)\begin{aligned} \widehat{f}_1-f_1=A^{-1}A\widehat{f}_1-A^{-1}Wf_0 \\ &=A^{-1}\left(A\widehat{f}_1-Wf_0\right). \tag*{(48)} \end{aligned}

By using (45), we can bound ∥f^1−f1∥\lVert\hat{f}_1-f_1\rVert as

∥f^1−f1∥≤m∥A∥∥A−1∥2η.(49)\lVert\hat{f}_1-f_1\rVert\le m\lVert A\rVert\lVert A^{-1}\rVert^2\eta. \tag*{(49)}

For k=2k=2 we have

∥f^2−f2∥≤∥f^2−A−1Wf^1∥+∥A−1Wf^1−f2∥=∥f^2−A−1Wf^1∥+∥A−1Wf^1−A−1Wf1∥≤m∥A∥∥A−1∥2η+∥A−1W∥∥f^1−f1∥≤(1+∥A−1W∥)m∥A∥∥A−1∥2η,\begin{aligned} \lVert\hat{f}_2-f_2\rVert&\le\lVert\hat{f}_2-A^{-1}W\hat{f}_1\rVert+\lVert A^{-1}W\hat{f}_1-f_2\rVert\\ &=\lVert\hat{f}_2-A^{-1}W\hat{f}_1\rVert+\lVert A^{-1}W\hat{f}_1-A^{-1}Wf_1\rVert\\ &\le m\lVert A\rVert\lVert A^{-1}\rVert^2\eta+\lVert A^{-1}W\rVert\lVert\hat{f}_1-f_1\rVert\\ &\le\left(1+\lVert A^{-1}W\rVert\right)m\lVert A\rVert\lVert A^{-1}\rVert^2\eta, \end{aligned}

where the last inequality follows from (49). More generally,

∥f^k−1−fk−1∥≤m∥A∥∥A−1∥2η∑j=0k−2∥A−1W∥j.(50)\lVert\hat{f}_{k-1}-f_{k-1}\rVert\le m\lVert A\rVert\lVert A^{-1}\rVert^2\eta\sum_{j=0}^{k-2}\lVert A^{-1}W\rVert^j. \tag*{(50)}

Repeating the string of inequalities above and replacing the right sum with the inductive hypothesis, we obtain

∥f^k−fk∥≤m∥A∥∥A−1∥2η∑j=0k−1∥A−1W∥j≤m∥A∥∥A−1∥21−∥A−1W∥η,(51)\begin{aligned} \lVert\hat{f}_k-f_k\rVert&\le m\lVert A\rVert\lVert A^{-1}\rVert^2\eta\sum_{j=0}^{k-1}\lVert A^{-1}W\rVert^j\\ &\le\frac{m\lVert A\rVert\lVert A^{-1}\rVert^2}{1-\lVert A^{-1}W\rVert}\eta, \tag*{(51)} \end{aligned}

which completes the proof.

Recall that the stability region of an explicit step-truncation method is the same as the corresponding method without truncation [40, 41]. Similarly, Theorem 2 shows that the stability region of an implicit step-truncation method is identical to the corresponding method without truncation, though by relaxing accuracy we see that instead our iterates decay to within the solver tolerance of zero rather than converging to zero in an infinite time horizon. In other words, both implicit step-truncation Euler and implicit step-truncation midpoint methods are unconditionally stable. However, if the tolerance of HT/TT-GMRES is set too large, then we could see poor stability behavior akin to an explicit method.

Numerical results

In this section we study the performance of the proposed implicit step-truncation methods in three numerical applications involving time-dependent PDEs. Specifically, we study the Allen-Cahn equation [35] in two spatial dimensions, the Fokker-Planck equation [39] in four dimensions, and the nonlinear Schrödinger equation [44] in six dimensions.

Allen-Cahn equation

The Allen-Cahn equation is a reaction-diffusion equation that describes the process of phase separation in multi-component alloy systems [1, 2]. In its simplest form, the equation has a cubic polynomial non-linearity (reaction term) and a diffusion term [29], i.e.,

∂f∂t=εΔf+f−f3.(52)\frac{\partial f}{\partial t}=\varepsilon\Delta f+f-f^3. \tag*{(52)}

In our application, we set ε=0.1\varepsilon=0.1, and solve (52) on the two-dimensional flat torus Ω=[0,2π]2\Omega=[0,2\pi]^2. We employ a second order splitting [22] method to solve the Laplacian Δf\Delta f as a fixed rank temporal integration and cubic f−f3f-f^3 term using our rank adaptive integration. The initial condition is set as

f0(x,y)=u(x,y)−u(x,2y)+u(3x+π,3y+π)−2u(4x,4y)+2u(5x,5y),(53)f_0(x,y)=u(x,y)-u(x,2y)+u(3x+\pi,3y+\pi)-2u(4x,4y)+2u(5x,5y), \tag*{(53)}

where

u(x,y)=[e−tan⁡2(x)+e−tan⁡2(y)]sin⁡(x)sin⁡(y)1+e∣csc⁡(−x/2)∣+e∣csc⁡(−y/2)∣.(54)u(x,y)=\frac{\left[e^{-\tan^2(x)}+e^{-\tan^2(y)}\right]\sin(x)\sin(y)}{1+e^{\lvert\csc(-x/2)\rvert}+e^{\lvert\csc(-y/2)\rvert}}. \tag*{(54)}

We discretize (52) in space using the two-dimensional Fourier pseudospectral collocation method [27] with 257×257257 \times257 points in Ω=[0,2π]2\Omega=[0,2\pi]^2. This results in a matrix ODE in the form of (4). We truncate the initial condition to absolute and relative SVD tolerances of 10−910^{-9}, which yields an initial condition represented by a 257×257257 \times257 matrix of rank 90. We also computed a benchmark solution of the matrix ODE using a variable step RK4 method with absolute tolerance set to 10−1410^{-14}. We denote the benchmark solution as freff_{\mathrm{ref}}. In Figure 3 we observe the transient accuracy of our order one and order two implicit methods. The stopping tolerance for inexact Newton’s iterations is set to εtol=2.2×10−8\varepsilon_{\mathrm{tol}}=2.2\times10^{-8}, while and HT/TT-GMRES relative error is chosen as η=10−3\eta=10^{-3}. Time integration was halted at t=14t=14. After this time, the system is close to steady state and the errors stay bounded near the final values plotted Figure 3. Similarly, the rank also levels out around t=14t=14. In Figure 4, we plot temporal evolution of the rank for both the implicit step-truncation Euler and midpoint methods.

Figure 3. Error versus time for step-truncation numerical solutions of Allen-Cahn equation (57) in dimension d=2d=2 with initial condition (53).

Figure 4. Rank versus time for step-truncation numerical solutions of Allen-Cahn equation (57) in dimension d=2d=2 with initial condition (53).

Due to the smoothing properties of the Laplacian, the high frequencies in the initial condition quickly decay and, correspondingly, the rank drops significantly within the first few time steps. Due to the rapidly decaying rank for this problem, we have plotted it in log scale. In Figure 5, we provide a comparison between the rank-adaptive implicit step-truncation midpoint method we propose here and the rank-adaptive explicit step-truncation midpoint method

Figure 5. Allen-Cahn equation (52). Comparison between the L2(Ω)L^2(\Omega) errors of explicit and implicit step-truncation midpoint methods for different Δt\Delta t.

fk+1=Tr3(fk+ΔtTr2(G(fk+Δt2Tr1(G(fk))))),(55)\mathbf{f}_{k+1}=\mathcal{T}_{r_3}\left(\mathbf{f}_k+\Delta t\mathcal{T}_{r_2}\left(G\left(\mathbf{f}_k+\frac{\Delta t}{2}\mathcal{T}_{r_1}\left(G(\mathbf{f}_k)\right)\right)\right)\right), \tag*{(55)}

which was recently studied in [40]. The truncation ranks r1r_1, r2r_2, and r3r_3 time-dependent and satisfy the order conditions

εr3≤AΔt3,εr2≤BΔt2,εr1≤GΔt.(56)\varepsilon_{r_3}\le A\Delta t^3,\qquad\varepsilon_{r_2}\le B\Delta t^2,\qquad\varepsilon_{r_1}\le G\Delta t. \tag*{(56)}

Such conditions guarantee that the scheme (55) is second-order convergent (see [40]). Figure 5 shows that the explicit step-truncation midpoint method undergoes a numerical instability for Δt=10−3\Delta t=10^{-3}. Indeed it is a conditionally stable method. The explicit step-truncation midpoint method also has other issues. In particular, in the rank-adaptive setting we consider here, we have that in the limit Δt→0\Delta t\to0 the parameters εr1\varepsilon_{r_1}, εr2\varepsilon_{r_2} and εr3\varepsilon_{r_3} all go to zero (see equation (56)). This implies that the truncation operators may retain all singular values, henceforth maxing out the rank and thereby giving up all computational gains of low-rank tensor compression. On the other hand, if Δt\Delta t is too large, then one we have stability issues as discussed above. Indeed, we see both these problems with the explicit step-truncation midpoint method, giving only a relatively narrow region of acceptable time step sizes in which the method is effective.

In Table 1 we provide a comparison between explicit and implicit step-truncation midpoint methods in terms of computational cost (CPU-time on an Intel Core I9-7980XE workstation) and accuracy at time t=14t=14. It is seen that the implicit step-truncation midpoint method is roughly 20 to 30 times faster than the explicit step-truncation midpoint method for a comparable error3. Moreover, solutions with a large time step (>10−3>10^{-3}) are impossible to achieve with the explicit step-truncation method due to time step restrictions associated with conditional stability.

ST Explicit MidpointST Implicit Midpoint
Δt\Delta tRuntime (seconds)∥f−fref∥\lVert f-f_{\mathrm{ref}}\rVertΔt\Delta tRuntime (seconds)∥f−fref∥\lVert f-f_{\mathrm{ref}}\rVert
1.0×10−31.0\times10^{-3}Did not finishUnstable1.0×10−11.0\times10^{-1}5.30975.30972.5652×10−22.5652\times10^{-2}
5.0×10−45.0\times10^{-4}2.2946×1022.2946\times10^{2}6.0713×10−36.0713\times10^{-3}5.0×10−25.0\times10^{-2}1.0495×1011.0495\times10^{1}7.7248×10−37.7248\times10^{-3}
2.5×10−42.5\times10^{-4}4.7828×1024.7828\times10^{2}5.2628×10−45.2628\times10^{-4}2.5×10−22.5\times10^{-2}1.8987×1011.8987\times10^{1}2.0977×10−32.0977\times10^{-3}
1.0×10−41.0\times10^{-4}1.2619×1031.2619\times10^{3}5.3648×10−55.3648\times10^{-5}1.0×10−21.0\times10^{-2}3.8025×1013.8025\times10^{1}6.7477×10−66.7477\times10^{-6}
5.0×10−55.0\times10^{-5}2.7354×1032.7354\times10^{3}1.1723×10−51.1723\times10^{-5}5.0×10−35.0\times10^{-3}7.6183×1017.6183\times10^{1}3.6012×10−63.6012\times10^{-6}

Table 1. Allen-Cahn equation (52). Comparison between explicit and implicit step-truncation midpoint methods in terms of computational cost (CPU-time on an Intel Core I9-7980XE workstation) and accuracy at final time (t=14t=14). It is seen that the implicit step-truncation midpoint method is roughly 20 to 30 times faster than the explicit step-truncation midpoint method for a comparable error.

Fokker-Planck equation

Fokker–Planck equation

Consider the Fokker–Planck equation

∂f(x,t)∂t=−∑i=1d∂∂xi(μi(x)f(x,t))+σ22∑i=1d∂2f(x,t)∂xi2(57)\frac{\partial f(x,t)}{\partial t}=-\sum_{i=1}^{d}\frac{\partial}{\partial x_i}\left(\mu_i(x)f(x,t)\right)+\frac{\sigma^2}{2}\sum_{i=1}^{d}\frac{\partial^2 f(x,t)}{\partial x_i^2} \tag*{(57)}

on a four-dimensional (d=4d=4) flat torus Ω=[0,2π]4\Omega=[0,2\pi]^4. The components of the drift are chosen as

μi(x)=(γ(xi+1)−γ(xi−2))ξ(xi−1)−ϕ(xi),i=1,…,d,(58)\mu_i(x)=\left(\gamma(x_{i+1})-\gamma(x_{i-2})\right)\xi(x_{i-1})-\phi(x_i),\qquad i=1,\ldots,d, \tag*{(58)}

where γ(x)=sin⁡(x)\gamma(x)=\sin(x), ξ(x)=exp⁡(sin⁡(x))+1\xi(x)=\exp(\sin(x))+1, and ϕ(x)=cos⁡(x)\phi(x)=\cos(x) are 2π2\pi-periodic functions. In (58) we set xi+d=xix_{i+d}=x_i. For this particular drift field, the right side of (57) can be split into a component tangential to the tensor manifold Hr\mathcal{H}_r and a component that is non-tangential as

∂f(x,t)∂t=∑i=1d(−γ(xi+1)ξ(xi−1)∂f(x,t)∂xi+γ(xi−2)ξ(xi−1)∂f(x,t)∂xi)⏟Not tangential+(∂∂xiϕ(xi)f(x,t)+σ22∂2f(x,t)∂xi2)⏟tangential.(59)\frac{\partial f(\boldsymbol{x},t)}{\partial t} = \sum_{i=1}^{d} \underbrace{\left(-\gamma(x_{i+1})\xi(x_{i-1})\frac{\partial f(\boldsymbol{x},t)}{\partial x_i}+\gamma(x_{i-2})\xi(x_{i-1})\frac{\partial f(\boldsymbol{x},t)}{\partial x_i}\right)}_{\text{Not tangential}}+\underbrace{\left(\frac{\partial}{\partial x_i}\phi(x_i)f(\boldsymbol{x},t)+\frac{\sigma^2}{2}\frac{\partial^2f(\boldsymbol{x},t)}{\partial x_i^2}\right)}_{\text{tangential}}. \tag*{(59)}

We solve (59) using an operator splitting method. To this end, we notice that there are 3d3d many terms in the summation above, and therefore we first solve the first dd time dependent PDEs which are tangential to the tensor manifold Hr\mathcal{H}_r, i.e.,

∂gi∂t=∂∂xiϕ(xi)gi+σ22∂2gi∂xi2,i=1,…,d.(60)\frac{\partial g_i}{\partial t}=\frac{\partial}{\partial x_i}\phi(x_i)g_i+\frac{\sigma^2}{2}\frac{\partial^2g_i}{\partial x_i^2},\qquad i=1,\ldots,d. \tag*{(60)}

Then we solve the non-tangential equations in two batches,

∂uj∂t=γ(xi+1)ξ(xi−1)∂uj∂xi,j=1,…,d(61)\frac{\partial u_j}{\partial t}=\gamma(x_{i+1})\xi(x_{i-1})\frac{\partial u_j}{\partial x_i},\qquad j=1,\ldots,d \tag*{(61)}
∂uk∂t=γ(xi−2)ξ(xi−1)∂uk∂xi,k=2,…,2d.(62)\frac{\partial u_k}{\partial t}=\gamma(x_{i-2})\xi(x_{i-1})\frac{\partial u_k}{\partial x_i},\qquad k=2,\ldots,2d. \tag*{(62)}

This yields the first-order (Lie-Trotter) approximation f(x,Δt)=u2d(x,Δt)+O(Δt2)f(\boldsymbol{x},\Delta t)=u_{2d}(\boldsymbol{x},\Delta t)+O(\Delta t^2). We also use these same list of PDEs for the second-order (Strang) splitting integrator. For each time step in both first- and second-order splitting methods, we terminate the HT/TT-GMRES iterations by setting the stopping tolerance ϵtol=10−9\epsilon_{\mathrm{tol}}=10^{-9}. We set the initial probability density function (PDF) as

f0(x1,x2,x3,x4)=1F0∑j=1M(∏i=14sin⁡((2j−1)xi−π/2)+122(j−1)+∏i=14exp⁡(cos⁡(2jxi+π))22j−1),(63)f_0(x_1,x_2,x_3,x_4)=\frac{1}{F_0}\sum_{j=1}^{M}\left(\prod_{i=1}^{4}\frac{\sin((2j-1)x_i-\pi/2)+1}{2^{2(j-1)}}+\prod_{i=1}^{4}\frac{\exp(\cos(2jx_i+\pi))}{2^{2j-1}}\right), \tag*{(63)}

where F0F_0 is a normalization constant. This gives an HTucker tensor with rank bounded by 2M2M. We set M=10M=10 to give ranks bounded by 20. We discretize (57)–(63) in Ω\Omega with the Fourier pseudospectral collocation method [27] on a tensor product grid with N=20N=20 evenly-spaced points along each coordinate xix_i, giving the total number of points (N+1)4=194481(N+1)^4=194481. This number corresponds to the number of entries in the tensor f(t)f(t) appearing in equation (4). Also, we set σ=5\sigma=5 in (57).

In Figure 6 we compare a few time snapshots of the marginal PDF

Marginal probability density functions for ST implicit Euler, ST implicit midpoint, and the reference solution at $t=0$, $t=0.1$, and $t=10$

Figure 6. Marginal probability density function (64) obtained by integrating numerically the Fokker–Planck equation (57) in dimension d=4d=4 with σ=5\sigma=5 and initial condition (63) with two methods: i) rank-adaptive implicit step-truncation Euler and ii) rank-adaptive implicit step-truncation midpoint. The reference solution is a variable time step RK4 method with absolute tolerance of 10−1410^{-14}. These solutions are computed on a grid with 20×20×20×2020\times20\times20\times20 interior points (evenly spaced). The steady state is determined for this computation by halting execution when ∥∂fref/∂t∥2\lVert\partial f_{\mathrm{ref}}/\partial t\rVert_2 is below a numerical threshold of 10−810^{-8}. This happens at approximately t≈10t\approx10 for the initial condition (63).

f12(x1,x2)=∫02π∫02πf(x1,x2,x3,x4) dx3dx4,(64)f_{12}(x_1,x_2)=\int_{0}^{2\pi}\int_{0}^{2\pi}f(x_1,x_2,x_3,x_4)\,\mathrm{d}x_3\mathrm{d}x_4, \tag*{(64)}

we obtained with the rank-adaptive implicit step-truncation Euler and midpoint methods, as well as the reference marginal PDF. The solution very quickly relaxes to nearly uniform by t=0.1t=0.1, then slowly rises to its steady state distribution by t=10t=10.

In Figure 7 we study accuracy and rank of the proposed implicit step-truncation methods in comparison with the rank-adaptive explicit Adams-Bashforth (AB) method of order 2 (see [40]). The implicit step-truncation methods use a time step size of Δt=10−3\Delta t=10^{-3}, while step-truncation AB2 uses a step size of Δt=10−4\Delta t=10^{-4}. The highest error and lowest rank come from the implicit step-truncation midpoint method with Δt=10−2\Delta t=10^{-2}. The highest rank and second highest error go to the step-truncation AB2 method, which runs with time step size 10−410^{-4} for stability. This causes a penalty in the rank, since as the time step is made small, the rank must increase to maintain convergence order (see, e.g., (56) for similar conditions on explicit step-truncation midpoint method) The implicit step-truncation midpoint method performs the best, with error of approximately 10−610^{-6} and rank lower than the step-truncation AB2 method at steady state. Overall, the proposed implicit step-truncation methods perform extremely well on linear problems of this form, especially when the right hand side is explicitly written as a sum of tensor products of one dimensional operators. In Figure 8 we show a plot of the convergence rate of implicit step-truncation Euler and midpoint methods. For this figure, we set σ=2\sigma=2. The convergence rates are order one and order two respectively, verifying Theorem 1.

Figure 7. L2(Ω)L^2(\Omega) error and rank versus time for numerical solutions of Fokker–Planck equation (57) in dimension d=4d=4 with initial condition (63). The rank plotted here is the largest rank for all tensors being used to represent the solution in HT format. Rank of the reference solution is in HT format.

Figure 8. L2(Ω)L^2(\Omega) errors at t=0.1t=0.1 for the implicit rank-adaptive step-truncation implicit Euler and midpoint methods versus Δt\Delta t. The reference solution of (57) if computed using a variable time step RK4 method with absolute tolerance of 10−1410^{-14}.

Nonlinear Schrödinger equation

The nonlinear Schrödinger equation is complex-valued PDE whose main applications are wave propagation in nonlinear optical fibers, and Bose-Einstein condensates [42, 44]. The equation can be written as4

∂ϕ(x,t)∂t=i2Δϕ(x,t)−iV(x)ϕ(x,t)−iε∣ϕ(x,t)∣2ϕ(x,t).(65)\frac{\partial\phi(x,t)}{\partial t}=\frac{i}{2}\Delta\phi(x,t)-iV(x)\phi(x,t)-i\varepsilon|\phi(x,t)|^2\phi(x,t). \tag*{(65)}

where V(x)V(x) is the particle interaction potential. In our example, we consider 6 particles trapped on a line segment in the presence of a double-well potential defined as

V(x)=∑k=16W(xk),W(xk)=[1+ecos⁡(xk)2+34(1+esin⁡(xk)2)]ηθ(xk).(66)V(x)=\sum_{k=1}^{6}W(x_k),\qquad W(x_k)=\left[1+e^{\cos(x_k)^2}+\frac{3}{4}\left(1+e^{\sin(x_k)^2}\right)\right]\eta_\theta(x_k). \tag*{(66)}

Here, W(xk)W(x_k) is a potential with barriers at xk=0x_k=0 and xk=πx_k=\pi (see Figure 9). The function ηθ(xi)\eta_\theta(x_i) is a mollifier which converges weakly to 1+δ(xi)+δ(xi−π)1+\delta(x_i)+\delta(x_i-\pi) as θ→0\theta\to0. One such mollifier is

Figure 9. Double-well potential (66)–(67) for different values of θ\theta. It is seen that as θ→0\theta\to0, the potential barrier at x=0x=0 and x=πx=\pi becomes infinitely high. This is identical to the well-known homogeneous boundary conditions for particles trapped in a box.

ηθ(x)=1+12πθ(exp⁡[−x22θ]+exp⁡[−(x−π)22θ]).(67)\eta_\theta(x)=1+\frac{1}{\sqrt{2\pi\theta}}\left(\exp\left[-\frac{x^2}{2\theta}\right]+\exp\left[-\frac{(x-\pi)^2}{2\theta}\right]\right). \tag*{(67)}

As θ→0\theta\to0, the weak limit of ηθ\eta_\theta translates to zero Dirichlet boundary conditions on the domain Ω=[0,π]6\Omega=[0,\pi]^6. The Dirichlet conditions naturally allow us to use a discrete sine transform to compute the Laplacian’s differentiation matrices. We discretize the domain Ω\Omega on a uniform grid with 35 points per dimension. This gives us a tensor with 356=83826562535^6=838265625 entries, or 14.7 Gigabytes per temporal solution snapshot if we store the uncompressed tensor in a double precision IEEE 754 floating point format. We choose a product of pure states for our initial condition, i.e.,

ϕ(x,0)=∏k=1661/64k2kπ−sin⁡(2πk)sin⁡(kxk),(68)\phi(x,0)=\prod_{k=1}^{6}\frac{6^{1/6}4^k}{2k\pi-\sin(2\pi k)}\sin(kx_k), \tag*{(68)}

The normalizing constant 61/64k/(2kπ−sin⁡(2πk))6^{1/6}4^k/(2k\pi-\sin(2\pi k)) guarantees that the wavefunction has an initial mass of 6 particles. We now apply an operator splitting method to solve (65). The linear components are all tangential

H(ϕ)=∫Ω(14∣∇ϕ∣2+12V(x)∣ϕ∣2+ε4∣ϕ∣4) dx.(69)H(\phi)=\int_{\Omega}\left(\frac{1}{4}|\nabla\phi|^2+\frac{1}{2}V(x)|\phi|^2+\frac{\varepsilon}{4}|\phi|^4\right)\,dx. \tag*{(69)}

to the tensor manifold Hr\mathcal{H}_r, and have a physical interpretation. Specifically,

∂gk∂t=i2∂2gk∂xk2−iW(xk)gk,k=1,…,6,(70)\frac{\partial g_k}{\partial t} = \frac{i}{2}\frac{\partial^2 g_k}{\partial x_k^2} - iW(x_k)g_k,\qquad k=1,\ldots,6, \tag*{(70)}

is a sequence of one-dimensional linear Schrödinger equations. The non-tangential part reduces to

dudt=iε∣u∣2u,(71)\frac{du}{dt} = i\varepsilon|u|^2u, \tag*{(71)}

which may be interpreted as an ODE describing all pointwise interactions of the particles. Here we set ε=10−4\varepsilon= 10^{-4} to model weak interactions. Clearly, the linear terms in (65) have purely imaginary eigenvalues. Therefore to integrate the semi-discrete form of (65) in time we need a numerical scheme that has the imaginary axis within its stability region. Since implicit step-truncation Euler method introduces a significant damping, thereby exacerbating inaccuracy due to discrete time stepping, we apply the implicit step-truncation midpoint method. For this problem, we set Δt=5×10−2\Delta t = 5 \times10^{-2} and the tensor truncation error to be constant in time at 100Δt3100\Delta t^3 to maintain second-order consistency. Tolerance of the inexact Newton method was set to 5×10−55 \times10^{-5} and the HT/TT-GMRES relative error to 5×η=10−45 \times\eta= 10^{-4}. In Figure 10 we plot the time-dependent marginal probability density functions for the joint position variables (xk,xk+1)(x_k,x_{k+1}), k=1,3,5k=1,3,5. Such probability densities are defined as

Figure 10. Marginal probability density functions representing particle positions generated by the nonlinear Schrödinger equation (65) with ε=10−4\varepsilon= 10^{-4}, interaction potential (66) and initial condition (68).

p(x1,x2,t)=16∫[0,1]4ϕ∗(x,t)ϕ(x,t) dx3dx4dx5dx6,(72)p(x_1,x_2,t) = \frac{1}{6}\int_{[0,1]^4}\phi^*(x,t)\phi(x,t)\,dx_3dx_4dx_5dx_6, \tag*{(72)}

and analogously for p(x3,x4,t)p(x_3,x_4,t) and p(x5,x6,t)p(x_5,x_6,t). It is seen that the lower energy pure states (position variables (x1,x2)(x_1,x_2)) quickly get trapped in the two wells, oscillating at their bottoms. Interestingly, at t=2.5t=2.5 it appears that particle x3x_3 is most likely to be observed in between the two wells whenever the particle x4x_4 is in a well bottom.

In Figure 11(a), we plot the rank over time for this problem. The rank also has physical meaning. A higher rank HT tensor is equivalent to a wavefunction with many entangled states, regardless of which L2(Ω)L^2(\Omega) basis we choose. In the example discussed in this section, the particles interacting over time monotonically increase the rank. We emphasize that the nonlinearity in (65) poses a significant challenge to tensor methods. In fact, in a single application of the function iε∣u∣2ui\varepsilon|u|^2u, we may end up tripling the rank. This can be mitigated somewhat by using the approximate element-wise tensor multiplication routine. Even so, if the inexact Newton Method requires many dozens of iterations to halt, the rank may grow very rapidly in a single time step, causing a slowing due to large array storage. This problem is particularly apparent when ε≈1\varepsilon\approx1 or if Δt\Delta t is made significantly smaller, e.g. Δt=10−4\Delta t=10^{-4}. A more effective way of evaluating nonlinear functions on tensors decompositions would certainly mitigate this issue. In Figure 11(b), we plot the relative error of the solution mass and the Hamiltonian (69) over time. The relative errors hover around 10−1110^{-11} and 10−610^{-6}, respectively. It is remarkable that even though the additional tensor truncation done after the inner loop of the implicit solver in principle destroys the symplectic properties of the midpoint method, the mass and Hamiltonian are still preserved with high accuracy.

Figure 11. (a) Maximum tensor rank versus time, and (b) relative error in the solution mass and Hamiltonian (69) for nonlinear Schrödinger equation (65) in dimension d=6d=6, with ε=10−4\varepsilon=10^{-4}, interaction potential (66) and initial condition (68).

Solving algebraic equations on tensor manifolds

We have seen in § 3 that a large class of implicit step-truncation methods can be equivalently formulated as a root-finding problem for a nonlinear system algebraic equations of the form

H(f)=0(73)H(f)=0 \tag*{(73)}

at each time step. In this appendix we develop numerical algorithms to compute an approximate solution of (A.1) on a tensor manifold Hr\mathcal{H}_r with a given rank rr. In other words, we are interested in finding f∈Hrf \in\mathcal{H}_r that solves (A.1) with controlled accuracy. To this end, we combine the inexact inexact Newton method [17 Theorem 2.3 and Corollary 3.5] with the TT-GMRES linear solver proposed in [20].

Theorem 3 (Inexact Newton method [17]). Let H:RN→RNH:\mathbb{R}^{N}\to\mathbb{R}^{N} be continuously differentiable in a neighbourhood of a zero f∗f^*, and suppose that the Jacobian of HH, i.e., JH(f)=∂H(f)/∂fJ_H(f)=\partial H(f)/\partial f, is invertible at f∗f^*. Given f[0]∈RNf^{[0]}\in\mathbb{R}^{N}, consider the sequence

f[j+1]=f[j]+s[j],j=0,1,…(74)f^{[j+1]}=f^{[j]}+s^{[j]},\qquad j=0,1,\ldots \tag*{(74)}

where each s[j]s^{[j]} solves the Newton iteration up to relative error η[j]\eta^{[j]}, i.e., it satisfies

∥JH(f[j])s[j]+H(f[j])∥≤∥H(f[j])∥η[j].(75)\left\|J_H\left(f^{[j]}\right)s^{[j]}+H\left(f^{[j]}\right)\right\|\leq\left\|H\left(f^{[j]}\right)\right\|\eta^{[j]}. \tag*{(75)}

If η[j]<1\eta^{[j]} < 1 for all jj, then there exists ε>0\varepsilon> 0 so that for any initial guess satisfying ∥f[0]−f∗∥<ε\left\|f^{[0]} - f^*\right\| < \varepsilon the sequence {f[j]}\{f^{[j]}\} converges linearly to f[∗]f^{[*]}. If η[j]→0\eta^{[j]} \to0 as j→∞j \to\infty, then the convergence speed is superlinear.

The next question is how to compute an approximate solution of the linear system

JH(f[j])s[j]=−H(f[j])(76)J_H\left(f^{[j]}\right)s^{[j]}=-H\left(f^{[j]}\right) \tag*{(76)}

satisfying the bound (A.3), without inverting the Jacobian JH(f[j])J_H\left(f^{[j]}\right) and assuming that s[j]∈Hrjs^{[j]} \in\mathcal{H}_{r_j}, i.e., that s[j]s^{[j]} is a tensor with rank rjr_j. To this end we utilize the relaxed HT/TT-GMRES method discussed in [20] HT/TT-GMRES is an adapted tensor-structured generalized minimal residual (GMRES) method to solve linear systems in a tensor format. The solver employs an indirect accuracy check and a stagnation restart check in its halting criterion which we summarize in the following Lemma.

Lemma 1 (Accuracy of HT/TT-GMRES [20]). Let Jf=bJf=b be a linear system where ff, bb are tensors in HT or TT format, and JJ is a bounded linear operator on ff. Let {f[0],f[1],…}\{f^{[0]},f^{[1]},\ldots\} be the sequence of approximate solutions generated by HT/TT-GMRES algorithm in [20], and ε>0\varepsilon>0 be the stopping tolerance for the iterations. Then

∥Jf[j]−b∥≤m∥J∥∥J−1∥∥b∥ε,(77)\left\|Jf^{[j]}-b\right\|\leq m\|J\|\|J^{-1}\|\|b\|\varepsilon, \tag*{(77)}

where mm is the number of Krylov iterations performed before restart. Similarly, the distance between f[j]f^{[j]} and the exact solution ff can be bounded as

∥f[j]−f∥≤m∥J∥∥J−1∥2∥b∥ε.(78)\left\|f^{[j]}-f\right\|\leq m\|J\|\|J^{-1}\|^2\|b\|\varepsilon. \tag*{(78)}

We can now combine the HT/TT-GMRES linear solver with the inexact Newton method, to obtain an algorithm that allows us to solve nonlinear algebraic equations of the form (A.1) on a tensor manifold.

Theorem 4 (HT/TT Newton method). Let H:Rn1×n2×⋯×nd→Rn1×n2×⋯×ndH:\mathbb{R}^{n_1\times n_2\times\cdots\times n_d}\to\mathbb{R}^{n_1\times n_2\times\cdots\times n_d} be a continuously differentiable nonlinear map which operates on HT or TT tensor formats, and let f∗f^* be a zero of HH. Suppose that the Jacobian of HH, denoted as JH(f)J_H(f), is invertible at f∗f^*. Given an initial guess f[0]f^{[0]}, consider the iteration

f[j+1]=Tr(f[j]+s[j])(79)f^{[j+1]}=\mathcal{T}_r\left(f^{[j]}+s^{[j]}\right) \tag*{(79)}

where s[j]s^{[j]} is the HT/TT-GMRES solution of JH(f[j])s[j]=−H(f[j])J_H\left(f^{[j]}\right)s^{[j]}=-H\left(f^{[j]}\right) satisfying

∥JH(f[j])s[j]+H(f[j])∥≤12∥H(f[j])∥η[j],(80)\left\|J_H\left(f^{[j]}\right)s^{[j]}+H\left(f^{[j]}\right)\right\|\leq\frac{1}{2}\left\|H\left(f^{[j]}\right)\right\|\eta^{[j]}, \tag*{(80)}

where η[j]\eta^{[j]} is the relative error, which can be any value in the range 0≤η[j]<10\leq\eta^{[j]}<1. Then the Newton iteration converges linearly so long as the rank rr of the truncation operator Tr\mathcal{T}_r is chosen to satisfy

∥Tr(f[j]+s[j])−f[j]−s[j]∥≤∥H(f[j])∥2∥J[j]∥η[j].(81)\left\|\mathcal{T}_r\left(f^{[j]}+s^{[j]}\right)-f^{[j]}-s^{[j]}\right\|\leq\frac{\left\|H\left(f^{[j]}\right)\right\|}{2\left\|J^{[j]}\right\|}\eta^{[j]}. \tag*{(81)}

Proof. Let f[0]f^{[0]} be an initial guess. Consider the sequence

f~[j+1]=f[j]+s[j]j=0,1,…(82)\widetilde{f}^{[j+1]}=f^{[j]}+s^{[j]}\qquad j=0,1,\ldots \tag*{(82)}

where s[j]s^{[j]} is the HT/TT-GMRES solution of JH(f[j])s[j]=−H(f[j])J_H\left(f^{[j]}\right)s^{[j]}=-H\left(f^{[j]}\right) obtained with tolerance

εj<η[j]2m∥JH(f[j])∥∥JH−1(f[j])∥,(83)\varepsilon_j<\frac{\eta^{[j]}}{2m\left\|J_H\left(f^{[j]}\right)\right\|\left\|J_H^{-1}\left(f^{[j]}\right)\right\|}, \tag*{(83)}

and 0≤η[j]<10\leq\eta^{[j]}<1. The next step is to truncate f~[j+1]\widetilde{f}^{[j+1]} to a tensor

f[j+1]=Tr(f~[j+1])(84)f^{[j+1]}=\mathcal{T}_r\left(\widetilde{f}^{[j+1]}\right) \tag*{(84)}

Figure A.12. Error versus iteration count of inexact Newton’s method in the HT format.

with rank rr chosen so that

∥f[j+1]−f~[j+1]∥<∥H(f[j])∥∥JH(f[j])∥η[j].(85)\left\|f^{[j+1]}-\widetilde{f}^{[j+1]}\right\| < \frac{\left\|H\left(f^{[j]}\right)\right\|}{\left\|J_H\left(f^{[j]}\right)\right\|}\eta^{[j]}. \tag*{(85)}

Then the error in solving the Newton iteration this step is

r~[j]=JH(f[j])[f[j+1]−f~[j+1]+sj]+H(f[j]),(86)\widetilde{r}^{[j]}=J_H\left(f^{[j]}\right)\left[f^{[j+1]}-\widetilde{f}^{[j+1]}+s^{j}\right]+H\left(f^{[j]}\right), \tag*{(86)}

which we constructed to satisfy the bound

∥r~[j]∥≤∥JH(f[j])s[j]+H(f[j])∥+∥JH(f[j])[f[j+1]−f~[j+1]]∥<∥H(f[j])∥η[j].(87)\left\|\widetilde{r}^{[j]}\right\|\leq\left\|J_H\left(f^{[j]}\right)s^{[j]}+H\left(f^{[j]}\right)\right\|+\left\|J_H\left(f^{[j]}\right)\left[f^{[j+1]}-\widetilde{f}^{[j+1]}\right]\right\|<\left\|H\left(f^{[j]}\right)\right\|\eta^{[j]}. \tag*{(87)}

Hence, the inexact HT/TT-GMRES Newton method converges linearly. This completes the proof.

An Example

Let us provide a brief numerical demonstration of the inexact Newton method with HT/TT-GMRES iteration. To this end, consider the cubic function

H(f)=1.5f+0.5f0+0.125(f+f0)3(88)H(f)=1.5f+0.5f_{0}+0.125(f+f_{0})^{3} \tag*{(88)}

where all products are computed using the approximate element-wise Hadamard tensor product with accuracies set to 10−1210^{-12}, and f0f_{0} is a given tensor which corresponds to the initial condition used in § 6.1 truncated to an absolute tolerance of 10−410^{-4}. The Jacobian operator is easily obtained as

JH(f)s=1.5s+0.375(f+f0)2s.(89)J_H(f)s=1.5s+0.375(f+f_{0})^{2}s. \tag*{(89)}

We set the relative error of the matrix inverse to be η=10−3\eta=10^{-3}. In Figure A.12 we plot the results of the proposed inexact Newton method with HT/TT-GMRES iterations. We see that that the target tolerance of 2.2×10−82.2\times10^{-8} is hit in just 12 iterations.

References

  1. [1]S. M. Allen and J. W. Cahn. Ground state structures in ordered binary alloys with second neighbor interactions. Acta Metall., 20(3):423–433, 1972.DOI
  2. [2]S. M. Allen and J. W. Cahn. A correction to the ground state of FCC binary ordered alloys with first and second neighbor pairwise interactions. Scripta Metallurgica, 7(12):1261–1264, 1973.DOI
  3. [3]W. Austin, G. Ballard, and T. G. Kolda. Parallel tensor compression for large-scale scientific data. In IPDPS’16: Proceedings of the 30th IEEE International Parallel and Distributed Processing Symposium, pages 912–922, May 2016.DOI
  4. [4]M. Bachmayr, R. Schneider, and A. Uschmajew. Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations. Found. of Comput. Math., 16(6), 2016.DOI
  5. [5]J. Baldeaux and M. Gnewuch. Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition. SIAM J. Numer. Anal., 52(3):1128–1155, 2014.
  6. [6]V. Barthelmann, E. Novak, and K. Ritter. High dimensional polynomial interpolation on sparse grids. Advances in Computational Mechanics, 12:273–288, 2000.DOI
  7. [7]M. J. Beran. Statistical continuum theories. New York: Interscience Publishers, 1968.
  8. [8]A. M. P. Boelens, D. Venturi, and D. M. Tartakovsky. Parallel tensor methods for high-dimensional linear PDEs. J. Comput. Phys., 375:519–539, 2018.DOI
  9. [9]A. M. P. Boelens, D. Venturi, and D. M. Tartakovsky. Tensor methods for the Boltzmann-BGK equation. J. Comput. Phys., 421:109744, 2020.DOI
  10. [10]H. J. Bungartz and M. Griebel. Sparse grids. Acta Numerica, 13:147–269, 2004.
  11. [11]Y. Cao, Z. Chen, and M. Gunzburger. ANOVA expansions and efficient sampling methods for parameter dependent nonlinear PDEs. Int. J. Numer. Anal. Model., 6:256–273, 2009.DOI
  12. [12]Y. Chen, L. Zhang, H. Wang, and W. E. Ground state energy functional with Hartree-Fock efficiency and chemical accuracy. J. Phys. Chem. A, 124(35), 2020.DOI
  13. [13]H. Cho, D. Venturi, and G.E. Karniadakis. Numerical methods for high-dimensional probability density function equations. J. Comput. Phys., 305:817–837, January 2016.
  14. [14]H. Al Daas, G. Ballard, and P. Benner. Parallel algorithms for tensor train arithmetic. SIAM J. Sci. Comput., 44(1):C25–C53, 2022.
  15. [15]A. Dektor and D. Venturi. Dynamically orthogonal tensor methods for high-dimensional nonlinear PDEs. J. Comput. Phys., 404:109125, 2020.DOI
  16. [16]A. Dektor and D. Venturi. Dynamic tensor approximation of high-dimensional nonlinear PDEs. J. Comput. Phys., 437:110295, 2021.DOI
  17. [17]Ron S. Dembo, Stanley C. Eisenstat, and Trond Steihaug. Inexact newton methods. SIAM Journal on Numerical Analysis, 19(2):400–408, 1982.DOI
  18. [18]G. Di Marco and L. Pareschi. Numerical methods for kinetic equations. Acta Numerica, 23:369–520, May 2014.
  19. [19]S. Dolgov, B. Khoromskij, and I. Oseledets. Fast solution of parabolic problems in the tensor train/quantized tensor train format with initial application to the Fokker–Planck equation. SIAM J. Sci. Comput., 34(6):A3016–A3038, 2012.DOI
  20. [20]S. V. Dolgov. TT-GMRES: solution to a linear system in the structured tensor format. Russian Journal of Numerical Analysis and Mathematical Modelling, 28(2):149–172, 2013.arxiv.org/abs/1206.5512
  21. [21]W. E, J. Han, and Q. Li. A mean-field optimal control formulation of deep learning. Res. Math. Sci., 6(10):1–41, 2019.
  22. [22]István Faragó and Agnes Havasiy. Operator splittings and their applications. Nova Science Publishers, 2009.
  23. [23]J. Foo and G. E. Karniadakis. Multi-element probabilistic collocation method in high dimensions. J. Comput. Phys., 229:1536–1557, 2010.DOI
  24. [24]L. Grasedyck. Hierarchical singular value decomposition of tensors. SIAM J. Matrix Anal. Appl., 31(4):2029–2054, 2010.DOI
  25. [25]L. Grasedyck and C. Löbbert. Distributed hierarchical SVD in the hierarchical Tucker format. Numer. Linear Algebra Appl., 25(6):e2174, 2018.arxiv.org/abs/1708.03340
  26. [26]E. Hairer, C. Lubich, and G. Wanner. Geometric numerical integration, volume 31 of Springer Series in Computational Mathematics. Springer-Verlag, Berlin, second edition, 2006. Structure-preserving algorithms for ordinary differential equations.
  27. [27]J. S. Hesthaven, S. Gottlieb, and D. Gottlieb. Spectral methods for time-dependent problems. Cambridge University Press, 2007.DOI
  28. [28]E. Hopf. Statistical hydromechanics and functional calculus. J. Rat. Mech. Anal., 1(1):87–123, 1952.DOI
  29. [29]A.-K. Kassam and L. N. Trefethen. Fourth-order time stepping for stiff PDEs. SIAM J. Sci. Comput., 26(4):1214–1233, 2005.DOI
  30. [30]B. N. Khoromskij. Tensor numerical methods for multidimensional PDEs: theoretical analysis and initial applications. In CEMRACS 2013–modelling and simulation of complex systems: stochastic and deterministic approaches, volume 48 of ESAIM Proc. Surveys, pages 1–28. EDP Sci., Les Ulis, 2015.DOI
  31. [31]E. Kieri and B. Vandereycken. Projection methods for dynamical low-rank approximation of high-dimensional problems. Comput. Methods Appl. Math., 19(1):73–92, 2019.DOI
  32. [32]D. Kressner and C. Tobler. Algorithm 941: htucker – a Matlab toolbox for tensors in hierarchical Tucker format. ACM Transactions on Mathematical Software, 40(3):1–22, 2014.
  33. [33]G. Li and H. Rabitz. Regularized random-sampling high dimensional model representation (RS-HDMR). J. Math. Chem., 43(3):1207–1232, 2008.DOI
  34. [34]L. Li, J. Qiu, and G. Russo. A high order semi-Lagrangian finite difference method for nonlinear Vlasov and BGK models. Comm. Appl. Math. Comput., 5:170–198, 2023.
  35. [35]H. Montanelli and Y. Nakatsukasa. Fourth-order time-stepping for stiff PDEs on the sphere. SIAM J. Sci. Comput., 40(1):A421–A451, 2018.arxiv.org/abs/1701.06030
  36. [36]A. Narayan and J. Jakeman. Adaptive Leja sparse grid constructions for stochastic collocation and high-dimensional approximation. SIAM J. Sci. Comput., 36(6):A2952–A2983, 2014.
  37. [37]M. Raissi and G. E. Karniadakis. Hidden physics models: Machine learning of nonlinear partial differential equations. J. Comput. Phys., 357:125–141, 2018.
  38. [38]M. Raissi, P. Perdikaris, and G. E. Karniadakis. Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. J. Comput. Phys., 378:686–707, 2019.
  39. [39]H. Risken. The Fokker-Planck equation: methods of solution and applications. Springer-Verlag, second edition, 1989. Mathematics in science and engineering, vol. 60.
  40. [40]A. Rodgers, A. Dektor, and D. Venturi. Adaptive integration of nonlinear evolution equations on tensor manifolds. J. Sci. Comput., 92(39):1–31, 2022.arxiv.org/abs/2008.00155
  41. [41]A. Rodgers and D. Venturi. Stability analysis of hierarchical tensor methods for time-dependent PDEs. J. Comput. Phys., 409:109341, 2020.DOI
  42. [42]S. H. Rudy, S. L. Brunton, J. L. Proctor, and J. N. Kutz. Data-driven discovery of partial differential equations. Science Adv., 3(4):e1602614, 2017.
  43. [43]T. Shi, M. Ruth, and A. Townsend. Parallel algorithms for computing the tensor-train decomposition. ArXiv, (2111.10448):1–23, 2021.arxiv.org/abs/2111.10448
  44. [44]A. Trombettoni and A. Smerzi. Discrete solitons and breathers with dilute Bose-Einstein condensates. Phys. Rev. Lett., 86:2353–2356, 2001.
  45. [45]A. Uschmajew. Local convergence of the alternating least squares algorithm for canonical tensor approximation. SIAM J. Matrix Anal. Appl., 33(2):639–652, 2012.DOI
  46. [46]A. Uschmajew and B. Vandereycken. The geometry of algorithms using hierarchical tensors. Linear Algebra Appl., 439(1):133–166, 2013.DOI
  47. [47]D. Venturi. The numerical approximation of nonlinear functionals and functional differential equations. Phys. Reports, 732:1–102, 2018.DOI
  48. [48]D. Venturi and A. Dektor. Spectral methods for nonlinear functionals and functional differential equations. Research in the Mathematical Sciences, 8(27):1–39, 2021.arxiv.org/abs/2003.14308
  49. [49]Y. Zhu, N. Zabaras, P.-S. Koutsourelakis, and P. Perdikaris. Physics-constrained deep learning for high-dimensional surrogate modeling and uncertainty quantification without labeled data. J. Comput. Phys., 394:56–81, 2019.DOI
  50. [50]J. Zinn-Justin. Quantum field theory and critical phenomena. Oxford Univ. Press, fourth edition, 2002.

Paper details

vlnc:W_5y9e9ww6
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