betaFeedback

WorksMathematics

Tensor approximation of functional differential equations

Abstract

Functional Differential Equations (FDEs) play a fundamental role in many areas of mathematical physics, including fluid dynamics (Hopf characteristic functional equation), quantum field theory (Schwinger-Dyson equation), and statistical physics. Despite their significance, computing solutions to FDEs remains a longstanding challenge in mathematical physics. In this paper we address this challenge by introducing new approximation theory and high-performance computational algorithms designed for solving FDEs on tensor manifolds. Our approach involves approximating FDEs using high-dimensional partial differential equations (PDEs), and then solving such high-dimensional PDEs on a low-rank tensor manifold leveraging high-performance parallel tensor algorithms. The effectiveness of the proposed approach is demonstrated through its application to the Burgers-Hopf FDE, which governs the characteristic functional of the stochastic solution to the Burgers equation evolving from a random initial state.

Introduction

Functional differential equations (FDEs) are equations involving operators (nonlinear functionals), and derivatives/integrals of such operators with respect functions (functional derivatives) and other independent variables such as space and time [1, 2]. FDEs arise naturally in many different branches of physics. A classical example in fluid dynamics is the Hopf-Navier-Stokes equation [3, 4, 5, 6]

∂Φ([θ],t)∂t=∑k=13∫Ωθk(x)(i∑j=13∂∂xjδ2Φ([θ],t)δθk(x)δθj(x)+ν∇2δΦ([θ],t)δθk(x)) dx(1)\frac{\partial\Phi([\theta],t)}{\partial t} = \sum_{k=1}^{3}\int_{\Omega}\theta_k(x)\left(i\sum_{j=1}^{3}\frac{\partial}{\partial x_j}\frac{\delta^2\Phi([\theta],t)}{\delta\theta_k(x)\delta\theta_j(x)}+\nu\nabla^2\frac{\delta\Phi([\theta],t)}{\delta\theta_k(x)}\right)\,dx \tag*{(1)}

which governs the temporal evolution of the characteristic functional

Φ([θ],t)=E{exp⁡(i∫Ωu(x,t)⋅θ(x) dx)}.(2)\Phi([\theta],t)=\mathbb{E}\left\{\exp\left(i\int_{\Omega}u(x,t)\cdot\theta(x)\,dx\right)\right\}. \tag*{(2)}

Here, Ω⊆R3\Omega\subseteq\mathbb{R}^3 is the spatial domain, u(x,t)u(x,t) represents a stochastic solution of the Navier-Stokes equations

∂u∂t+(u⋅∇)u=−∇p+ν∇2u,∇⋅u=0,(3)\begin{aligned} \frac{\partial u}{\partial t}+(u\cdot\nabla)u&=-\nabla p+\nu\nabla^2u,\\ \nabla\cdot u&=0, \tag*{(3)} \end{aligned}

corresponding to a random initial velocity distribution [7, 8], E{⋅}\mathbb{E}\{\cdot\} is the expectation over the probability measure of such random velocity distribution, and θ(x)\theta(x) is a divergence-free test function. Equation (1) involves derivatives of the functional Φ([θ],t)\Phi([\theta],t) with respect to the functions θi(x)\theta_i(x), i.e., functional derivatives δ/δθi(x)\delta/\delta\theta_i(x) [2], and derivatives with respect to the independent variables xjx_j and tt.

As is well-known, the characteristic functional (2) encodes the full statistical information of the random field u(x,t)u(x,t) that solves the Navier-Stokes equations (3), including multi-point statistical moments, cumulants, and multi-point joint probability density functions. For instance, by taking functional derivatives of Φ\Phi we can immediately express the mean and auto-correlation function of u(x,t)u(x,t) as

E{uk(x,t)}=1iδΦ([θ],t)δθk(x)∣θ=0,(4)\mathbb{E}\{u_k(x,t)\}=\left.\frac{1}{i}\frac{\delta\Phi([\theta],t)}{\delta\theta_k(x)}\right|_{\theta=0}, \tag*{(4)}
E{uk(x,t)uj(y,t)}=1i2δ2Φ([θ],t)δθk(x)δθj(y)∣θ=0.(5)\mathbb{E}\{u_k(x,t)u_j(y,t)\}=\left.\frac{1}{i^2}\frac{\delta^2\Phi([\theta],t)}{\delta\theta_k(x)\delta\theta_j(y)}\right|_{\theta=0}. \tag*{(5)}

Similarly, by evaluating (2) at θi(x)=aiδ(x−y)\theta_i(x)=a_i\delta(x-y) yields the one-point characteristic function of the solution u(y,t)u(y,t) at an arbitrary spatial location y∈Ωy\in\Omega as

ϕ(a,y,t)=E{exp⁡(i∫Ωu(x,t)⋅aδ(x−y) dx)}=E{eia⋅u(y,t)}.(6)\phi(a,y,t)=\mathbb{E}\left\{\exp\left(i\int_{\Omega}u(x,t)\cdot a\delta(x-y)\,dx\right)\right\} =\mathbb{E}\left\{e^{ia\cdot u(y,t)}\right\}. \tag*{(6)}

The inverse Fourier transform (in the sense of distributions) of ϕ(a,y,t)\phi(a,y,t) with respect to the variable aa is the probability density function PDF of the solution u(y,t)u(y,t) at the spatial location y∈Ωy\in\Omega and time tt. Any other statistical property of u(x,t)u(x,t) can be derived from the characteristic functional (2). For this reason, the FDE (1) was deemed by Monin and Yaglom ([4, Ch. 10) to be “the most compact formulation of the general turbulence problem”, which is the problem of determining the statistical properties of the velocity and the pressure fields of the Navier-Stokes equations given statistical information on the initial state.

Another well-known classical example of functional differential equation is the Schwinger-Dyson (SD) equation of quantum field theory [9, 10]. The SD equation describes the dynamics of the generating functional of the Green functions of a quantum field theory, allowing us to propagate quantum field interactions in a perturbation setting (e.g., with Feynman diagrams), or in a strong coupling regime. The usage of FDEs saw rapid growth in the 1970s, driven by the realization that techniques originally developed for quantum field theory by Dyson, Feynman, and Schwinger could be, at least formally, extended to other branches of mathematical physics. A pivotal contribution to this evolution was the groundbreaking work by Martin, Siggia, and Rose [11]. This work served as a landmark in the field, showcasing the possibility of applying quantum field theoretic methods, such as functional integrals and diagrammatic expansions [12, 13, 14, 15], to problems in classical statistical physics.

More recently, FDEs have appeared in both mean-field games and mean-field optimal control [16, 17]. Mean-field games are optimization problems involving a large (potentially infinite) number of interacting players. In some cases, it is possible to reformulate such optimization problems in terms of a nonlinear Hamilton-Jacobi-Bellman FDE in a Wasserstein space of probability measures. The standard form of such equation is (see [18 p. 1])

∂F([ρ],t)∂t+W([ρ],[δF([ρ],t)δρ(x)])=0,\frac{\partial F([\rho],t)}{\partial t}+\mathcal{W}\left([\rho],\left[\frac{\delta F([\rho],t)}{\delta\rho(x)}\right]\right)=0,
F([ρ],0)=F0([ρ]),(7)F([\rho],0)=F_0([\rho]), \tag*{(7)}

where ρ(x)\rho(x) is a dd-dimensional probability density function supported on R⊆RdR\subseteq\mathbb{R}^d, δF/δρ(x)\delta F/\delta\rho(x) is the first-order functional derivative of FF relative to ρ(x)\rho(x), and W\mathcal{W} is the Hamilton functional

W([ρ],[δF([ρ],t)δρ(x)])=∫RΨ(x,∇δF([ρ],t)δρ(x))ρ(x)dx+J([ρ]).(8)\mathcal{W}\left([\rho],\left[\frac{\delta F([\rho],t)}{\delta\rho(x)}\right]\right)=\int_R\Psi\left(x,\nabla\frac{\delta F([\rho],t)}{\delta\rho(x)}\right)\rho(x)dx +\mathcal{J}([\rho]). \tag*{(8)}

Here, Ψ\Psi is the Hamilton’s function and J([ρ])\mathcal{J}([\rho]) is an interaction potential. Mean-field theory is also useful in optimal feedback control of nonlinear stochastic dynamical systems and in deep learning. For instance, E and collaborators [17] established the mathematical groundwork for the population risk minimization problem in deep learning by framing it as a mean-field optimal control problem. This yields yields a generalized version of the Hamilton-Jacobi-Bellman equation in a Wasserstein space of probability measures, which is a nonlinear FDE of the form (6) – e.g., equation (20) in [17] and equation (1.1) in [19].

In this paper we develop approximation theory and high-performance computational algorithms designed for solving FDEs on tensor manifolds. Our approach involves first approximating FDEs in terms of high-dimensional partial differential equations (PDEs), and then computing the solution to such high-dimensional PDEs on a low-rank tensor manifold leveraging high-performance (parallel) tensor algorithms. To this end, we will build upon our recent work on tensors, in particular step-truncation tensor methods [20, 21], and demonstrate convergence to functional approximations of FDEs.

This paper is organized as follows. In Section II we briefly review necessary and sufficient conditions for existence and uniqueness of solutions to FDEs. In Section III we discuss functional approximation of FDEs in terms of high-dimensional PDEs. In Section IV we briefly review numerical tensor methods approximate the solution of high-dimensional PDEs on tensor manifolds. In Section IV we demonstrate the new functional approximation methods for FDEs to the Burgers-Hopf equation. The main findings are summarized in Section VI. We also include Appendix A in which we describe the high-performance (parallel) tensor algorithms we developed to solve high-dimensional PDEs corresponding to FDEs on tensor manifolds.

Existence and uniqueness of solutions to FDEs

Let us briefly describe what the problem is here, and our intended course of action. To this end, consider the Hopf-Navier-Stokes functional differential equation (1). Back in 1972 Monin and Yaglom stated in [4 p. 773] that:

“When we tried to develop a complete statistical description of turbulence with the aid of the Hopf equation for the characteristic functional we found that no general mathematical formalism for solving linear equations in functional derivatives was available. There are also no rigorous theorems on the existence and uniqueness of the solution to such equations.}”

Since then, there were advancements in the theory of existence and uniqueness of solutions to the FDE (1). In particular, it was found the existence of a solution to (1) is strongly related to the existence of a Hopf-Leray weak solution for the Cauchy problem of the Navier-Stokes equations, which is a well-established result [22, 23, 24, 25] (see also [26 Theorem 3.1]). Specifically, it can be proved that if there exists a Hopf-Leray solution to the Navier-Stokes equations then there exists a statistical solution to the Hopf-Navier-Stokes equation (1) (see [27 §5 in Ch. 4]). A similar results was obtained by Foias in [8 p. 254] for initial velocity conditions described by probability measures with finite second moments.

Regarding uniqueness of the solution to the Hopf-Navier-Stokes equation (1), it turns out that this is again connected to the uniqueness of Hopf-Leray weak solutions to the Navier-Stokes equation. Indeed, Vishik and Fursikov proved in [27 Theorem 6.1] that if there exists a unique Hopf-Leray solution to the Navier-Stokes equation then any space-time statistical solution of the Hopf-Navier-Stokes equation is uniquely determined by the initial probability measure (see also [8 pp. 323-344]). In two spatial dimensions it is well-known that there exists a unique global Hopf-Leray solution, and therefore a unique statistical solution. The proof was formalized by Gishlarkaev in [28] for the Hopf-Navier-Stokes equation using techniques developed in [27]. The uniqueness of the Hopf-Leray solution for the three-dimensional Navier-Stokes equations is still an open problem, and a rather active area of research. For example, it can be shown that the Hopf-Leray solution is unique within at least a short-time integration period if we choose the initial condition in non-conventional function spaces [23, 24, 25, 29, 30]. Also, the Hopf-Leray solution is unique and global in time if we choose the initial data small enough [25, 31]. Recently, Galdi proved in [32] that very weak solutions to the Cauchy problem for the Navier-Stokes equations must be Hopf-Leray solutions if their initial data are solenoidal with finite kinetic energy. A smooth (mild or strong) solution of the Navier-Stokes equations is of course also a Hopf-Leray (weak) solution. More precisely, it can be shown that a mild solution to Navier-Stokes in HsH^s agrees with a weak Hopf-Leray solution almost everywhere in [0,T∗)[0,T^*). This result, which belongs to the so-called weak-strong uniqueness methods [33], implies that weak Hopf-Leray solutions are unique as long as a mild (or a strong) solution exists. In particular, Leray-Hopf solutions are unique whenever they are regular enough to be strong solutions. Once the strong solution is integrated past t∼T∗t \sim T^* (maximum Cauchy development), the is no further guarantee of uniqueness [25, 34]. We also recall that if the energy inequality that characterizes Hopf-Leray weak solutions is dropped then it is possible to construct multiple weak solutions of the Navier-Stokes equations with finite kinetic energy [35]. On the other hand, weak solutions obeying the energy inequality are necessarily unique and smooth if they lie in Lp([0,T])⊗Lq(Ω)L^p([0,T]) \otimes L^q(\Omega) with 2/p+3/q=12/p+3/q=1 and q>3q>3. These conditions are known as Prodi-Serrin-Ladyzhenskaya conditions, and they have been recently generalized in various ways (see [23, 36, 37]).

Approximation of FDEs by high-dimensional PDEs

Consider a well-posed initial/boundary value problem for an FDE, i.e., a problem that admits a unique solution in some function space as discussed in Section II. How do we compute the solution? This is a longstanding problem in mathematical physics and a rather new research area of computational mathematics.

The FDEs (1) and (6) can be seen as PDEs in an infinite number of independent variables. Such infinite-dimensional PDEs may be approximated by PDEs in a finite (though possibly extremely large) number of variables using the functional analytic methods described in [1, 2, 18, 19]. For instance, we have shown in [1, 2] that equation (1) can be approximated by the high-dimensional linear PDE

∂ϕ∂t=∑p=1nap(ν∑k=1nBpk∂ϕ∂ak+i∑j,k=1nApjk∂2ϕ∂ak∂aj)(9)\frac{\partial\phi}{\partial t}=\sum_{p=1}^{n}a_p\left(\nu\sum_{k=1}^{n}B_{pk}\frac{\partial\phi}{\partial a_k}+i\sum_{j,k=1}^{n}A_{pjk}\frac{\partial^2\phi}{\partial a_k\partial a_j}\right) \tag*{(9)}

where

ap=∫Ωθ⋅Γp dx,Bpk=∫ΩΓp⋅∇2Γk dx,a_p=\int_{\Omega}\theta\cdot\Gamma_p\,dx,\qquad B_{pk}=\int_{\Omega}\Gamma_p\cdot\nabla^2\Gamma_k\,dx,
Apjk=∫ΩΓp⋅[(Γk⋅∇)Γj] dx(10)A_{pjk}=\int_{\Omega}\Gamma_p\cdot[(\Gamma_k\cdot\nabla)\Gamma_j]\,dx \tag*{(10)}

{Γ1(x),…,Γn(x)}\{\Gamma_1(x),\ldots,\Gamma_n(x)\} is a divergence-free basis, and ϕ(a1,…,an,t)\phi(a_1,\ldots,a_n,t) is the characteristic function approximating the characteristic functional Φ[θ],t)\Phi[\theta],t) in the following sense:

ϕ(a1,…,an,t)=Φ[Pnθ],t),(11)\phi(a_1,\ldots,a_n,t)=\Phi[P_n\theta],t), \tag*{(11)}

where PnP_n is an orthogonal projection onto {Γ1,…,Γn}\{\Gamma_1,\ldots,\Gamma_n\}. The divergence-free basis {Γ1,…,Γn}\{\Gamma_1,\ldots,\Gamma_n\} can be constructed in terms of div-free wavelets [38, 39], radial basis functions [40], trigonometric polynomials [41], or eigenvalue problems for the Stokes operator with appropriate boundary conditions [22]. Approximating the FDE (1) using the PDE (8) bears a resemblance, in a certain aspect, to what is known as the “method of lines” for discretizing a nonlinear partial differential equation into a high-dimensional system of nonlinear ordinary differential equations (ODEs). However, in the context of FDEs, the “lines” are determined by a hyper-dimensional PDE instead of a system of ODEs.

In [2 Theorem 7.1] we proved that if we choose the test function θ(x)\theta(x) in a Sobolev sphere S(Ω)S(\Omega) of H1(Ω)H^1(\Omega)-div functions (which is a compact subset of L2(Ω)L^2(\Omega)-div) then ϕ\phi converges uniformly to the characteristic functional Φ\Phi as the number of independent variables nn goes to infinity, i.e.,

lim⁡n→∞sup⁡θ∈S(Ω)sup⁡t∈[0,T]∣ϕ(a1,…,an,t)−Φ[θ],t)∣=0.(12)\lim_{n\to\infty}\sup_{\theta\in S(\Omega)}\sup_{t\in[0,T]}|\phi(a_1,\ldots,a_n,t)-\Phi[\theta],t)|=0. \tag*{(12)}

Moreover, convergence of the high-dimensional PDE to the FDE can be exponential. The result (11) leverages the Trotter-Kato approximation theorem [42 p. 210] for abstract evolution equations in Banach spaces [43]. Gangbo et al. [19] proved a similar result for the nonlinear functional HJB equation (6). Specifically, by evaluating the functional equation (6) on the Wasserstein space P2(Rd)\mathcal{P}_2(\mathbb{R}^d) (space of probability densities in Rd\mathbb{R}^d with finite second-order moment) with elements

ρn(x)=1n∑k=1nδ(x−xk),x,xi∈Rd(13)\rho_n(x)=\frac{1}{n}\sum_{k=1}^{n}\delta(x-x_k),\qquad x,x_i\in\mathbb{R}^d \tag*{(13)}

then we can write the FDE (6) as a hyper-dimensional nonlinear PDE

∂f∂t+1n∑k=1nΨ(xi,∂f∂xk)+j(x1,…,xn)=0(14)\frac{\partial f}{\partial t}+\frac{1}{n}\sum_{k=1}^{n}\Psi\left(x_i,\frac{\partial f}{\partial x_k}\right)+j(x_1,\ldots,x_n)=0 \tag*{(14)}

where f(x1,…,xn,t)=F([ρn],t)f(x_1,\ldots,x_n,t)=F([\rho_n],t) (see [19 Eq.(1.2)]). Moreover, if we choose the empirical measure (12) in a bounded subset BB of the Wasserstein space P2(Rd)\mathcal{P}_2(\mathbb{R}^d) then f(x1,…,xn,t)f(x_1,\ldots,x_n,t) converges uniformly to the (unique) solution of (6) as nn goes to infinity ([19 Theorem 1.2]), i.e.,

lim⁡n→∞sup⁡ρn∈Bt∈[0,T]∣f(x1,…,xn,t)−F([ρn],t)∣=0.(15)\lim_{n\to\infty}\sup_{\substack{\rho_n\in B\\ t\in[0,T]}}\left|f(x_1,\ldots,x_n,t)-F([\rho_n],t)\right|=0. \tag*{(15)}

The boundedness assumption of BB is essential for convergence. Similarly, the compactness assumption of the function space SS in (11) is essential for convergence (see [2 Theorems 7.1 and 8.3]).

To solve high-dimensional PDEs such as (8) and (13) numerically, we need a computational paradigm for linear PDEs that can handle tens, hundreds, or thousands of independent variables efficiently. Such computational paradigm is discussed in the next section.

Tensor approximation of high-dimensional PDEs

We have seen in Section III that FDEs can be approximated by high-dimensional PDEs of the form

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

where f:Ω×[0,T]→Rf:\Omega\times[0,T]\to\mathbb{R} is an nn-dimensional time-dependent scalar field defined on the domain Ω⊆Rn\Omega\subseteq\mathbb{R}^n, TT is the period of integration, and G\mathcal{G} is a nonlinear operator which may depend on the variables x=(x1,…,xn)∈Ωx=(x_1,\ldots,x_n)\in\Omega, and may incorporate boundary conditions. For simplicity, we assume that the domain Ω\Omega is a Cartesian product of nn one-dimensional domains Ωi\Omega_i

Ω=Ω1×⋯×Ωn,(17)\Omega=\Omega_1\times\cdots\times\Omega_n, \tag*{(17)}

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(Ωn)H(\Omega;[0,T])\simeq H([0,T])\otimes H(\Omega_1)\otimes\cdots\otimes H(\Omega_n) and represent the solution of (15) as

f(x,t)≈∑i1=1m1⋯∑in=1mnfi1…in(t)hi1(x1)⋯hin(xn),(18)f(x,t)\approx\sum_{i_1=1}^{m_1}\cdots\sum_{i_n=1}^{m_n}f_{i_1\ldots i_n}(t)h_{i_1}(x_1)\cdots h_{i_n}(x_n), \tag*{(18)}

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

dfdt=G(f),f(0)=f0(19)\frac{d f}{d t}=\mathcal{G}(f),\qquad f(0)=f_0 \tag*{(19)}

where f:[0,T]→Rm1×m2×⋯×mnf:[0,T]\to\mathbb{R}^{m_1\times m_2\times\cdots\times m_n} is a multivariate array with coefficients fi1…id(t)f_{i_1\ldots i_d}(t), and G\mathcal{G} is the finite-dimensional representation of the nonlinear operator G\mathcal{G}. The number of degrees of freedom associated with the solution to the Cauchy problem (18) is Ndof=m1m2⋯mnN_{\mathrm{dof}}=m_1m_2\cdots m_n at each time t≥0t\geq0, which can be extremely large even for moderately small dimension nn. For instance, the solution of the Boltzmann-BGK equation on a six-dimensional (n=6n=6) flat torus [44, 45] with mi=128m_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 [46, 47, 48] and techniques based on deep neural networks [49, 50].

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 [51, 52, 53, 54, 55, 56]. A tensor network is a factorization of an entangled object such as a multivariate function or an operator into simpler objects, e.g., low-dimensional functions or separable operators, which are amenable to efficient representation and computation. A tensor network can be visualized in terms of graphs (see Figure 1). The vast majority of tensor algorithms currently available to approximate functions, operators and PDEs on tensor spaces is based on canonical polyadic (CP) decompositions [44, 53, 56, 58], Tucker tensors, or tensors corresponding to binary trees such as tensor train (TT) [59, 60, 61] and hierarchical Tucker (HT) tensors [62, 63, 64, 65]. A compelling reason for using binary trees is that they allow to construct the tensor expansion by leveraging the spectral theory for linear operators, in particular the hierarchical Schmidt decomposition [59, 66, 67, 68, 69].

Image not extracted

Figure 1. Examples of tensor networks. The vertices represent tensor modes (functions) used in the decomposition. The edges connecting to vertices represent summation over an index (contraction) between two modes. The free edges represent input variables xjx_j (j=1,…,nj=1,\ldots,n).

Step-truncation tensor methods

A new class of algorithms to integrate (18) on a low-rank tensor manifold was recently proposed in [20, 21]. These algorithms are known as step-truncation methods and they are based on integrating the solution f(t)f(t) of the ODE (18) 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. To briefly describe these methods, let us discretize the ODE (18) in time with a one-step method on an evenly-spaced temporal grid as

fk+1=ΨΔt(G,fk),f0=f(0),(20)f_{k+1}=\Psi_{\Delta t}(\mathcal{G},f_k),\qquad f_0=f(0), \tag*{(20)}

where fkf_k denotes an approximation of f(kΔt)f(k\Delta t) for k=0,1,…k=0,1,\ldots and ΨΔt\Psi_{\Delta t} is an increment function. To obtain a step-truncation integrator, we simply apply a truncation operator TS(⋅)\mathcal{T}_{\mathcal{S}}(\cdot), i.e., a nonlinear projection onto a tensor manifold Ms\mathcal{M}_s of HT (or TT) tensors with multilinear rank ss [70], to the scheme (20) (see Figure 2). This yields

Image not extracted

Figure 2. Sketch of implicit and explicit step-truncation integration methods. Given a tensor fkf_k with multilinear rank ss on the tensor manifold Ms\mathcal{M}_s, we first perform an explicit time-step with any conventional time-stepping scheme. The explicit step-truncation integrator then projects ΨΔt(G,fk)\Psi_{\Delta t}(G,f_k) to a tensor manifold with rank ss. The multilinear rank ss is chosen adaptively based on desired accuracy and stability constraints [20]. 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 fk[j]f_k^{[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 Ms\mathcal{M}_s. This operation is equivalent to the compression step in the HT/TT-GMRES algorithm described in [57].

fk+1=Ts[ΨΔt(G,fk)].(21)f_{k+1}=\mathcal{T}_s\left[\Psi_{\Delta t}(G,f_k)\right]. \tag*{(21)}

The need for tensor rank-reduction when iterating (20) 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 [71].

We now present the rank-adaptive step-truncation algorithms used here to integrate FDEs on tensor manifolds. The first one is a truncated version of the Euler forward scheme, i.e.,

fk+1=Tr[fk+ΔtTs[G(fk)]].(22)f_{k+1}=\mathcal{T}_r\left[f_k+\Delta t\mathcal{T}_s[G(f_k)]\right]. \tag*{(22)}

We have shown that this scheme is convergent to first-order in Δt\Delta t provided the rank rr is properly updated at each time step [20] for details). The second step-truncation scheme is derived from the explicit midpoint rule, and it is defined as

fk+1=Tα[fk+ΔtTβ[G(fk+Δt2Tγ(G(fk)))]],(23)f_{k+1}=\mathcal{T}_{\alpha}\left[f_k+\Delta t\mathcal{T}_{\beta}\left[G\left(f_k+\frac{\Delta t}{2}\mathcal{T}_{\gamma}(G(f_k))\right)\right]\right], \tag*{(23)}

where α\alpha, β\beta, and γ\gamma are once again selected adaptively as time integration advances.

Both (22) and (23) are explicit step-truncation methods. These schemes are very simple to implement and have proven successful in integrating initial value problems for a variety of PDEs [20]. However, the combination of dimensionality, non-linearity and stiffness may introduce time-step restrictions which could make explicit time integration on tensor manifolds computationally infeasible. To overcome this problem, we recently developed a new class of implicit rank-adaptive step-truncation algorithms for temporal integration PDEs on tensor manifolds [21]. These algorithms are based on an inexact Newton’s method with tensor train GMRES iterations [57] to solve the algebraic equation arising from time discretization on the tensor manifold.

To describe these methods, let us consider the standard Euler backward scheme

fk+1=fk+ΔtG(fk+1),(24)f_{k+1}=f_k+\Delta tG(f_{k+1}), \tag*{(24)}

and the associated root-finding problem

Hk(fk+1)=fk+1−fk−ΔtG(fk+1)=0.(25)H_k(f_{k+1})=f_{k+1}-f_k-\Delta tG(f_{k+1})=0. \tag*{(25)}

If GG is linear, e.g., for PDEs of the form (9), this reduces to a linear inversion problem

(I−ΔtG)fk+1=fk.(26)(I-\Delta tG)f_{k+1}=f_k. \tag*{(26)}

To solve the linear system (26) in a tensor format, we apply the TT-GMRES method proposed by Dolgov in [57]. For the implicit midpoint method, the logic is identical. We apply the above steps to the linear system

(I−12ΔtG)fk+1=(I+12ΔtG)fk.(27)\left(I-\frac{1}{2}\Delta tG\right)f_{k+1}=\left(I+\frac{1}{2}\Delta tG\right)f_k. \tag*{(27)}

For the fully nonlinear case, one may couple the TT-GMRES iteration to an inexact Newton method and retain all convergence properties (see [21], Appendix A) for further details). In [21] we have recently show that under mild conditions on the tensor truncation error, the implicit step-truncation Euler and implicit step-truncation midpoint converge, respectively, with order one and order two in Δt\Delta t.

Burgers-Hopf FDE

Consider Burger’s equation on the unit circle Ω=[0,2π]\Omega= [0,2\pi]

∂u∂t+u∂u∂x=γ∂2u∂x2+R(u),(28)\frac{\partial u}{\partial t}+u\frac{\partial u}{\partial x}=\gamma\frac{\partial^2u}{\partial x^2}+R(u), \tag*{(28)}

with a reaction term R(u)=αsin⁡(πu)R(u)=\alpha\sin(\pi u) and random (2π2\pi-periodic) initial condition u(x,0)u(x,0). Let

Φ([θ(x)],t)=E{exp⁡(i∫02πu(x,t)θ(x)dx)}(29)\Phi([\theta(x)],t)=\mathbb{E}\left\{\exp\left(i\int_0^{2\pi}u(x,t)\theta(x)dx\right)\right\} \tag*{(29)}

be the characteristic functional of the stochastic solution to (27). It is straightforward to show that Φ([θ(x)],t)\Phi([\theta(x)],t) satisfies the following Burgers-Hopf FDE

∂Φ([θ],t)∂t=∫02π[i2∂∂xδ2Φ([θ],t)δθ(x)2+γ∂2∂x2δΦ([θ],t)δθ(x)+α∑k=1∞(−π)k(2k+1)!i2kδ2k+1Φ([θ],t)δθ(x)2k+1]θ(x)dx,(30)\frac{\partial\Phi([\theta],t)}{\partial t}=\int_0^{2\pi}\left[\frac{i}{2}\frac{\partial}{\partial x}\frac{\delta^2\Phi([\theta],t)}{\delta\theta(x)^2}+\gamma\frac{\partial^2}{\partial x^2}\frac{\delta\Phi([\theta],t)}{\delta\theta(x)}+\alpha\sum_{k=1}^{\infty}\frac{(-\pi)^k}{(2k+1)!i^{2k}}\frac{\delta^{2k+1}\Phi([\theta],t)}{\delta\theta(x)^{2k+1}}\right]\theta(x)dx, \tag*{(30)}

which admits a unique solution due to the uniqueness of the solution to the weak form of the Burgers equation (see Section II).

By approximating the FDE (29) in terms of a high-dimensional PDEs of the form of (8) and taking the inverse Fourier transform (in the sense of distributions) yields the Liouville-type linear hyperbolic conservation law

∂p∂t=−∑i=1N∂∂uj[∑j=1N(−uiDij(1)uj+δijR(uj)+γDij(2)uj)p],(31)\frac{\partial p}{\partial t}=-\sum_{i=1}^{N}\frac{\partial}{\partial u_j}\left[\sum_{j=1}^{N}\left(-u_iD_{ij}^{(1)}u_j+\delta_{ij}R(u_j)+\gamma D_{ij}^{(2)}u_j\right)p\right], \tag*{(31)}

where δij\delta_{ij} is the Kronecker delta and p(u1,u2,…,uN,t)p(u_1,u_2,\ldots,u_N,t) is the joint probability density function of the solution to (27) at all evenly-spaced grid points xj=2π(j−1)/Nx_j=2\pi(j-1)/N (j=1,…,Nj=1,\ldots,N), i.e., uj=u(xj,t)u_j=u(x_j,t).

In (30), Dij(1)D_{ij}^{(1)} and Dij(2)D_{ij}^{(2)} are differentiation matrices. In our numerical experiments, we use the second-order finite difference matrix on a periodic domain. From here, it is straightforward to write down a step-truncation tensor method to solve the high-dimensional PDE (30).

However, this may not yield an accurate scheme due to the properties of the solution. In fact, it is well-known that PDF equations of the form (30) can develop shocks [72], or can have solutions converging to Dirac delta functions if the time asymptotic solution is deterministic. In these cases, it is convenient to first transform the kinetic equation into a cumulative distribution function (CDF) equation via an integral transform [73], and then solve such CDF equation. This allows us to transform PDF shocks into CDF ramps, and PDF Dirac deltas into CDF shocks. In other words, the CDF equations produces solutions with features that are well-known to the numerical analysis community (shocks, ramps and solutions with range bounded in [0,1][0,1]) and therefore can be handled with numerical schemes for hyperbolic conservation laws [74].

By integrating (30) with respect to the phase variables {u1,…,uN}\{u_1,\ldots,u_N\} and using we obtain the following CDF equation

∂F∂t=∑i,j=1N(uiDij(1)uj−γDij(2)uj−δijR(uj))∂F∂ui−∑i,j=1i≠jN(Dij(1)ui−γDij(2))∫−∞uj∂F∂uidui−α∑j=1Nsin⁡(πuj)∂F∂uj,(32)\frac{\partial F}{\partial t}=\sum_{i,j=1}^{N}\left(u_iD_{ij}^{(1)}u_j-\gamma D_{ij}^{(2)}u_j-\delta_{ij}R(u_j)\right)\frac{\partial F}{\partial u_i} -\sum_{\substack{i,j=1\\i\ne j}}^{N}\left(D_{ij}^{(1)}u_i-\gamma D_{ij}^{(2)}\right)\int_{-\infty}^{u_j}\frac{\partial F}{\partial u_i}du_i -\alpha\sum_{j=1}^{N}\sin(\pi u_j)\frac{\partial F}{\partial u_j}, \tag*{(32)}

where

F(u1,…,un,t)=∫−∞u1⋯∫−∞unp(v1,…,vn,t)dv1⋯dvn.(33)F(u_1,\ldots,u_n,t)=\int_{-\infty}^{u_1}\cdots\int_{-\infty}^{u_n}p(v_1,\ldots,v_n,t)dv_1\cdots dv_n. \tag*{(33)}

With the CDF F(u1,…,uN,t)F(u_1,\ldots,u_N,t) available it is straightforward to compute the PDF

p(u1,…,uN,t)=∂NF(u1,…,uN,t)∂u1⋯∂uN.(34)p(u_1,\ldots,u_N,t)=\frac{\partial^N F(u_1,\ldots,u_N,t)}{\partial u_1\cdots\partial u_N}. \tag*{(34)}

To apply the proposed step-truncation tensor methods to equation (31), we discretize the phase space in terms of a NN-dimensional hypercube centered at the origin which covers the support of p(u1,u2,…uN,t)p(u_1,u_2,\ldots u_N,t). For the specific application at hand such hypercube is Σ=[−1.3,1.3]N\Sigma=[-1.3,1.3]^N. On the boundary of Σ\Sigma, it is straightforward to show that the derivative of FF normal to the hypercube boundary is zero. Therefore we may apply outflow boundary conditions, i.e., set ∂F/∂uj=0\partial F/\partial u_j=0 at the boundary of Σ\Sigma. We discretize each variable uiu_i in Σ\Sigma on an evenly-spaced grid with ni=64n_i=64 points. Also, we approximate the integrals in (31) using the trapezoidal rule, and the partial derivatives with centered second-order finite differences. For the initial condition, we set the CDF to be a product of NN zero-mean Gaussian CDFs with standard deviation σ=0.25\sigma=0.25, i.e.,

F(u1,…,uN,0)=∏k=1Ng(uk),(35)F(u_1,\ldots,u_N,0)=\prod_{k=1}^{N}g(u_k), \tag*{(35)}

where

g(u)=12[1+erf⁡(uσ2)](36)g(u)=\frac{1}{2}\left[1+\operatorname{erf}\left(\frac{u}{\sigma\sqrt{2}}\right)\right] \tag*{(36)}

and erf⁡(x)\operatorname{erf}(x) is the standard error function.

Numerical results

To solve the high-dimensional CDF equation (32) approximating the Burgers-Hopf FDE (30) we developed a high-performance (parallel) tensor code implementing the step truncation tensor methods discussed in Section IV A. The code can be found at the GitHub repository: https://github.com/akrodger/paratt.

We first perform a numerical study to verify temporal accuracy of order 1 and order 2 of the proposed step-truncation tensor methods applied to the high-dimensional CDF equation (32) (see Figure 3). To stabilize explicit step-truncation methods, we add a numerical diffusion term proportional to the round-off error in Δt\Delta t to the right hand side of (32), in a similar manner to the Lax-Wendroff method [75]. To guarantee that we are accurately capturing second and first order errors in time, we must ensure that the semi-discrete PDE we are solving for our reference solution matches that of our step-truncation integrators. To this end, we compute the local truncation errors of each scheme by computing its difference with a Richardson extrapolation [76 II.4] of it to 1 order higher, i.e., we take two steps of size Δt/2\Delta t/2 and combine it with a step of size Δt\Delta t to create a more accurate estimate for the purposes of comparing it to a single step of size Δt\Delta t. To this end, we calculate the local truncation errors by computing the difference between the prediction of each scheme and a Richardson extrapolation of one order higher (as outlined in [76 II.4]). In other words, we take two steps of size Δt/2\Delta t/2 and integrate them with a step of size Δt\Delta t to generate a more precise estimation for comparison with a single step of size Δt\Delta t. The results are shown in Figure 4. It is seen that the explicit/implicit Euler and explicit/implicit midpoint step-truncation integrators have accuracy of order one and order two, respectively. To quantify the errors, we constructed a benchmark CDF via Monte-Carlo simulation. In practice, we sampled 5×1065 \times10^6 initial conditions u(x,0)u(x, 0) from the Gaussian distribution described above, computed the solution u(x,t)u(x, t) of (27) using the Fourier pseudospectral method [77], and then used a kernel density estimator (KDE) [78] to obtain the one-point and the two-points CDFs. This allows us to study convergence of the solutions to the CDF equation (31) as we increase the dimension NN of the PDE. This convergence study is crucial for establishing convergence of the solution of the CDF equation (31) to the solution of the Burgers-Hopf FDE. For this analysis, we selected the explicit step-truncation midpoint tensor method as the temporal integrator, due to its favorable performance and ease of implementation.

Image not extracted

Figure 3. Sketch of the logical flow to transform a random nonlinear initial value problem (IVP) for the Burgers equation into the (linear) Burgers-Hopf FDE, which is linear. The Burgers-Hopf FDE is subsequently approximated using the methods outlined in Section III. This yields an NN-dimensional characteristic function equation of the form (8). By taking the inverse Fourier transform of such characteristic function equation and integrating it with respect to the phase variable we obtain the NN-dimensional CDF equation shown above. The CDF equation is then solved using the proposed step-truncation tensor methods.

Image not extracted

Figure 4. Local truncation errors (calculated as O(Δtp+1)O(\Delta t^{p+1}) for and order pp method) of the proposed step-truncation tensor methods. These errors are computed by comparing one time step of step-truncation method with its Richardson extrapolation. It is seen that explicit/implicit Euler and explicit/implicit midpoint step-truncation methods have accuracy of order one and order two, respectively.

In Figure 5 plot the joint CDF of u(0,t)u(0, t) and u(π,t)u(\pi, t) at t={0,0.04,0.08,0.012}t = \{0, 0.04, 0.08, 0.012\} computed with Monte Carlo, and the proposed step-truncation midpoint tensor method applied to a 20-dimensional (N=20N = 20) CDF equation (31). Clearly there is visual agreement between the results form the tensor simulation and the results form Monte-Carlo simulation. In Figure 6 we demonstrate convergence of the solution to the CDF equation (31) the Burgers-Hopf FDE as we increase the dimension NN from 8 to 20. The error plot in Figure 6 represents the L2L^2 error between the joint CDFs shown in Figure 5. Runtime increases considerably with dimension though, especially for moderately high solution ranks. For example once rank surpasses 100, the N=20N = 20 case requires approximately 45 minutes per time step on an Intel i9-7980xe workstation. The storage of the CDF tensor solution in 20 dimensions requires approximately 690 megabytes per temporal snapshot for tensor ranks of the order of 150. This is a significant compression of a multidimensional double precision floating point array of size 642064^{20}, which would normally require approximately 102210^{22} petabytes. That is to say that we capture O(10−2)O(10^{-2}) accuracy of the data while achieving a data compression ratio of 1.44×1026%1.44 \times10^{26}\% and data space savings of approximately 100%100\%.

Image not extracted

Figure 5. Two joint CDF of u(0,t)u(0,t) and u(π,t)u(\pi,t). The CDF is computed by generating numerical solutions to (32) for N=20N=20 using the proposed step-truncation tensor methods, and then marginalizing the solution in the remaining 18 variables. We also show a Monte-Carlo estimate of the joint CDF obtained by sampling 5×1065 \times10^{6} solutions to (28).

Figure 6. Left: Highest rank of the Tensor Train cores for tensor solutions of the CDF to equation (32) computed with the explicit step-truncation midpoint method for dimension N={8,12,16,20}N = \{8, 12, 16, 20\}. Right: Convergence of the solution to the CDF equation (31) the Burgers-Hopf FDE as we increase the dimension NN from 8 to 20. The error plot represents the L2L^2 error between the joint CDFs shown in Figure 5.

Of course, 690 megabytes is not negligible on practical computing systems. It is essentially nothing compared to the decompressed data though. In Figure 7 we compare the CDF of u(0,t)u(0,t) computed by solving the CDF equation (31) with N={8,12,16,20}N = \{8, 12, 16, 20\} and then marginalizing, with a benchmark CDF obtained by Monte-Carlo simulation of (27). It is seen that as we increase the dimension NN the marginal of the CDF tensor solution approaches the Monte-Carlo benchmark. While the proposed numerical tensor schemes are accurate and provably convergent, they may not preserve important properties of the CDF solution, such as positivity, monotonicity, and range in [0,1][0,1]. The development of a structure-preserving tensor integration schemes is indeed a rather unexplored research area. One possibility is to enforce structure at the level of the tensor truncation operation, i.e., perform rounding conditional to some required property. For instance, if we are interested in enforcing non-negativity in a step-truncation tensor scheme, then we can simply replace the truncation operator based on recursive QR decomposition (see Appendix A), with the distributed non-negative tensor truncation discussed in [79]. Another approach to enforce structure can be built directly at the level of the tensor equations. This approach was recently proposed by Einkemmer et al. in [80, 81, 82] in the context of Vlasov and Vlasov-Poisson kinetic equations. The resulting dynamical low-rank algorithm conserves mass, momentum, and energy.

Image not extracted

Figure 7. CDF of u(0,t)u(0,t) computed by solving equation (32) with the proposed step-truncation tensor method. It is seen that as we increase the dimension NN (number of independent variables in the CDF equation (32)) the tensor solution converges to the Monte-Carlo benchmark (black continuous line).

Summary

The numerical simulation of functional differential equations (FDEs) remains an open problem in many respects. In this paper, we developed approximation theory and new high-performance computational algorithms to solve FDEs on tensor manifolds. Our approach involves initially approximating the given FDE with a high-dimensional partial differential equation (PDE) using the functional approximation methods described in [1, 2, 19]. Subsequently, we compute the numerical solution of such PDE using parallel rank-adaptive step-truncation methods [20, 21]. This is a novel and effective strategy for computing numerical solutions to FDEs, which paves the way for further research and practical applications across various branches of physics and engineering. We demonstrated the effectiveness of the proposed new approach through its application to the Burgers-Hopf FDE, which governs the characteristic functional of the stochastic solution to the Burgers equation evolving from a random initial state. Our numerical results and convergence studies demonstrate that, despite their computational complexity, tensor methods allow us to compute accurate solutions to the Burgers-Hopf FDE.

Acknowledgments

This research was supported by the U.S. Army Research Office grant W911NF1810309. Dr. Rodgers would like to acknowledge the Transformational Tools and Technologies (T3) Project for partially funding his Ph.D. research through the NASA Pathways internship program.

Tensor algorithms

In this Appendix, we describe the high-performance (parallel) tensor algorithms we developed to solve high-dimensional PDEs on tensor manifolds, in particular the CDF equation discussed in § 1.4. To this end, we begin with a brief review of the algebraic representation of the tensor train format [83].

Tensor train decomposition

A tensor in f∈Rn1×n2×⋯×ndf \in\mathbb{R}^{n_1 \times n_2 \times\cdots\times n_d} is in a tensor train (TT) format if there is an array of positive integers (called the TT rank) r=(r0,r1,r2,…,rd−1,rd)\boldsymbol{r} = (r_0,r_1,r_2,\ldots,r_{d-1},r_d) with r0=1=rdr_0 = 1 = r_d and a list of order 3 tensors (called the TT cores) C=(C1,C2,…,Cd)\boldsymbol{C} = (C_1,C_2,\ldots,C_d) where Ck∈Rrk−1×nk×rkC_k \in\mathbb{R}^{r_{k-1} \times n_k \times r_k} such that the entries of ff may be written as the iterated matrix product

f[i1,i2,…,id]=C1[1,i1,:]C2[:,i2,:]⋯Cd−1[:,id−1,:]Cd[:,id,1],(37)f[i_1,i_2,\ldots,i_d] = C_1[1,i_1,:]C_2[:,i_2,:]\cdots C_{d-1}[:,i_{d-1},:]C_d[:,i_d,1], \tag*{(37)}

where the colon operator indicates multidimensional array slicing, akin to its usage in MATLAB. Though rather involved at first glance, the above expression may be derived by writing down a multivariate function series expansion by the method of separation of variables, rearranging the expression into a finite sequence of infinite matrix products, truncating the series so that the matrix products are finite, then discretizing in space so that the multivariate function is sampled on a tensor product grid. From this perspective, it becomes apparent that the tensor train cores represent a two-dimensional array of functions of a single variable and the ranks are the number of functions present in a series expansion approximation. A more concrete exploration of this perspective is given in [84, 85].

Due the the iterated matrix product definition of the format, it becomes apparent that a number of arithmetic operations may be represented in the format by producing a new TT tensor with different ranks. In particular if f,gf,g have TT core lists C,DC,D then by a simple inductive argument, we have

f[i1,i2,…,id]+g[i1,i2,…,id]=[C1[1,i1,:]D1[1,i1,:]][C2[:,i2,:]00D2[:,i2,:]]⋯[Cd−1[:,id−1,:]00Dd−1[:,id−1,:]][Cd[:,id,1]Dd[:,id,1]].(38)f[i_1,i_2,\ldots,i_d]+g[i_1,i_2,\ldots,i_d] = \begin{bmatrix} C_1[1,i_1,:] & D_1[1,i_1,:] \end{bmatrix} \begin{bmatrix} C_2[:,i_2,:] & 0 \\ 0 & D_2[:,i_2,:] \end{bmatrix} \cdots \begin{bmatrix} C_{d-1}[:,i_{d-1},:] & 0 \\ 0 & D_{d-1}[:,i_{d-1},:] \end{bmatrix} \begin{bmatrix} C_d[:,i_d,1] \\ D_d[:,i_d,1] \end{bmatrix}. \tag*{(38)}

Thus the sum w=f+gw=f+g is a TT tensor with cores obtained by concatenating those of ff and gg. Scalar multiplication is straightforward, just scale any of the cores of the tensor.

αf[i1,i2,…,id]=(αC1[1,i1,:])C2[:,i2,:]⋯Cd−1[:,id−1,:]Cd[:,id,1].(39)\alpha f[i_1,i_2,\ldots,i_d] = (\alpha C_1[1,i_1,:])C_2[:,i_2,:]\cdots C_{d-1}[:,i_{d-1},:]C_d[:,i_d,1]. \tag*{(39)}

In order to perform more sophisticated operations such as tensor truncations, we must frequently reshape the tensor cores into lower dimensional arrays. Two particularly useful reshapings are the horizontal flattening

H:Ra×b×c⟶Ra×(bc)H:\mathbb{R}^{a \times b \times c} \longrightarrow\mathbb{R}^{a \times(bc)}
C[i,j,k]⟼H[i,j+bk],C[i,j,k] \longmapsto H[i,j+bk],

and the vertical flattening,

V:Ra×b×c⟶R(ab)×cV:\mathbb{R}^{a \times b \times c} \longrightarrow\mathbb{R}^{(ab) \times c}
C[i,j,k]⟼V[i+aj,k].C[i,j,k] \longmapsto V[i+aj,k].

The above maps are two dimensional array analogs of the vectorization of a tensor, in which we have the coordinates are listed as C[i,j,k]=v[i+aj+abk]C[i,j,k]=v[i+aj+abk]. Note that when the entries of a tensor are stored contiguously in computer memory, no memory movement or copying needs to be done to interpret a tensor as its flattening or vectorization. To undo the flattening in an algorithm, we denote copying all the entries as C[:]=H[:]C[:] = H[:] or C[:]=V[:]C[:] = V[:].

The general procedure of truncating the ranks of a TT tensor comes in two phases. The first phase is to collect

Algorithm 1: Left Orthogonalization
Data: A tensor ff in TT format with cores (C1,C2,…,Cd)(C_1,C_2,\ldots,C_d).
Result: A tensor g=fg=f in TT format with left orthogonal cores.
Reserve memory for each core DcD_c with sizes of CcC_c.
D1=C1D_1=C_1
for c=1,2,…,d−1c=1,2,\ldots,d-1 do
[Qc,Rc]=QR(V(Dc))[Q_c,R_c]=QR(V(D_c))
Hc+1=RcH(Cc+1)H_{c+1}=R_cH(C_{c+1})
Dc[:]=Qc[:]D_c[:]=Q_c[:]
Dc+1[:]=Hc+1[:]D_{c+1}[:]=H_{c+1}[:]
end
Set the cores of gg as (D1,D2,…,Dd)(D_1,D_2,\ldots,D_d)
Algorithm 2: Truncation of a TT tensor
Data: A tensor ff in TT format with cores (C1,C2,…,Cd)(C_1,C_2,\ldots,C_d) and a desired accuracy ε\varepsilon.
Result: A tensor gg so that ∥g−f∥≤ε\lVert g-f\rVert\leq\varepsilon in TT format with right orthogonal cores.
Reserve memory for each core DcD_c with sizes of CcC_c.
Set (C^1,C^2,…,C^d)(\widehat{C}_1,\widehat{C}_2,\ldots,\widehat{C}_d) as orthogonal by Alg. 1.
ε^=ε/d−1\widehat{\varepsilon}=\varepsilon/\sqrt{d-1}
D1=C^1D_1=\widehat{C}_1
for c=d,d−1,…,2c=d,d-1,\ldots,2 do
[Uc,Σc,VcT]=SVD(H(Dc),ε^)[U_c,\Sigma_c,V_c^{\mathsf{T}}]=SVD(\mathsf{H}(D_c),\widehat{\varepsilon}) (Truncated SVD)
Hc−1=V(C^c−1)UcΣcH_{c-1}=\mathsf{V}(\widehat{C}_{c-1})U_c\Sigma_c
Dc[:]=Uc[:]D_c[:]=U_c[: ]
Dc−1[:]=Hc−1[:]D_{c-1}[:]=H_{c-1}[: ]
end
Set the cores of gg as (D1,D2,…,Dd)(D_1,D_2,\ldots,D_d)

Table 1.

all the norm of the tensor into a single core through a sequence of matrix factorizations, leaving all other cores to have Frobenius norm 1. Then a sequence of SVDs are applied, multiplying a non-unitary factor from a tensor train core to its neighboring cores. The first phase is called orthogonalization of a TT tensor and we now present an algorithm for it.

There are two variants of orthogonalization we will discuss. One is Left-to-Right orthogonalization and the other Right-to-Left orthogonalization. They are the same algorithm mirrored across the middle core of the tensor train and each step in one is a transpose of its counterpart in the other. A TT tensor is left orthogonal if for c=1,2,…,d−1c=1,2,\ldots,d-1, we have V(Cc)TV(Cc)=IV(C_c)^{\mathsf{T}}V(C_c)=I. Similarly, a TT tensor is right orthogonal if for c=2,3,…,dc=2,3,\ldots,d, we have H(Cc)H(Cc)T=IH(C_c)H(C_c)^{\mathsf{T}}=I. One may transform the cores of a TT tensor to be left orthogonal while the full tensor is unchanged by applying iterated matrix factorizations. All we must do is sequentially flatten, orthogonalize by QR decomposition, then unflatten each core, until the final one is reached. This process is summarized in Algorithm 1. For the right orthogonal case, the procedure is largely identical, though we use LQ factorization, the lower-triangular orthogonalizing decomposition, instead.

We now describe one algorithm for truncation of a tensor train given an orthogonalized TT tensor. The process is essentially the same as orthogonalization, we apply a sequence of orthogonal matrix factorizations to each core, multiplying one of the terms into that core’s left or right neighbor. We then replace the current core with the entries of an orthogonal factor. The difference in this algorithm is that we apply an SVD, rather than QR or LQ factorization. The term “truncation” comes from truncating the singular value decomposition series expansion of a matrix up to a desired tolerance. This truncation is described as the rounding algorithm in [86]. We present the right orthogonal variant of it here as Algorithm 2. There is no clear general rule for preferring one left or right variants truncation algorithm. They have identical computational costs and similar formulations. It is possible that differing runtime will occur based on row-major versus column major layout of the matrices, though this is highly dependent on the specific memory mapping and workspaces used in the SVD, QR, and LQ calls.

Parallel algorithms for tensor train arithmetic

Among the arithmetic operations performed on the tensor train during the evolution of the solution to a differential equation, the most costly is the truncation. This is due to the fact that it requires data access and editing of every core twice. Due to the sequential nature of the loops in Algorithms 1 and 2 we see that parallelizing the inner loop would be most effective. To this end, we follow the approach of [87]. Our extension of the algorithms presented in [87] can be found at the GitHub repository: https://github.com/akrodger/paratt. Since the rank of the tensor train is expected to change frequently during program execution, we must split the memory stored on a total of PP compute nodes in a manner independent of the tensor rank.

To this end, we introduce a P×dP\times d memory partition matrix MM with positive integer values so that for each core Ck∈Rrk−1×nk×rkC_k\in\mathbb{R}^{r_{k-1}\times n_k\times r_k}, we have ∑p=1PM[p,k]=nk\sum_{p=1}^{P}M[p,k]=n_k. This matrix describes a block-tensor storage layout for the tensor train core list. More precisely, for each core CkC_k, we define an array of core blocks (Ck1,Ck2,…,CkP)(C_k^1,C_k^2,\ldots,C_k^P) with array sizes defined via Ckp∈Rrk−1×M[p,k]×rkC_k^p\in\mathbb{R}^{r_{k-1}\times M[p,k]\times r_k} so that

Ck[i,:,j]=[Ck1[i,:,j]Ck2[i,:,j]⋮CkP[i,:,j]].(40)C_k[i,:,j]= \begin{bmatrix} C_k^1[i,:,j]\\ C_k^2[i,:,j]\\ \vdots\\ C_k^P[i,:,j] \end{bmatrix}. \tag*{(40)}

Each distributed memory compute node with index pp stores the core list (C1p,C2p,…,Cdp)(C_1^p,C_2^p,\ldots,C_d^p). This memory layout is designed so that

V(Ck)=[V(Ck1)V(Ck2)⋮V(CkP)]andH(Ck)=[H(Ck1)∣H(Ck2)∣⋯∣H(CkP)].V(C_k)= \begin{bmatrix} V(C_k^1)\\ V(C_k^2)\\ \vdots\\ V(C_k^P) \end{bmatrix} \qquad\text{and}\qquad H(C_k)=[H(C_k^1)\mid H(C_k^2)\mid\cdots\mid H(C_k^P)].

We may therefore compute a flattening of the cores without any memory movements or cross-node communications by reinterpreting the array storage offsets in column major layout. Additionally, sums and scalar multiplications of tensors may also be computed in parallel without communications.

This parallel layout also allows for straightforward applications of finite difference stencils. Consider a finite difference stencil which requires ss many points where the number of 1 dimensional ghost cells required is gg = (s−1)/2(s-1)/2. Let DFD\mathbf{D}_{\mathrm{FD}} be the linear operator for this stencil. To apply a partial derivative in variable kk to a TT tensor, we replace the entries of core CkC_k with the entries of DFD\mathbf{D}_{\mathrm{FD}} applied to equation (A4) for each i,ji,j. To perform the parallel version of this stencil, we first perform a nonblocking communication to deliver the ghost cells of compute node pp to their neighboring nodes p±1p \pm1. For nodes p=1p=1 or p=Pp=P, we instead rely on discrete boundary condition formulas, communicating again between nodes p=1p=1 and p=Pp=P if periodic boundary conditions are required. After boundary condition communications, every processor has an appropriate local version of the finite difference stencil, which is identical save for the definition of the ghost cells.

Numerical integration is similar, though instead of sharing ghost cells of compute node pp with compute node p±1p \pm1, we need only pass the data with compute node p+1p+1, due to the one-sided stencil of a cumulative summation formula.

Parallel tall-skinny QR factorization

In order to truncate a TT tensor with the described block memory layout, we must perform a distributed memory QR factorization on a matrix of the form

A=[A1A2⋮AP]A = \begin{bmatrix} A_1 \\ A_2 \\ \vdots\\ A_P \end{bmatrix}

or equivalently, perform an LQ factorization on the horizontally concatenated transpose of AA. For mathematical simplicity, we only present the QR variant, though our GitHub code available at https://github.com/akrodger/paratt has both variants. One such factorization amenable to this layout is the Tall-Skinny QR (TSQR) factorization [88]. This algorithm uses a binary tree structure to define a communication pattern for decomposing the QR factorization of AA into a collection of smaller QR factorizations, avoiding communications if possible. By factoring the blocks into their own QR factorizations, we see that the QQ factor may be presented as a sequence of products of block diagonal matrices. This process is then applied to a recursive binary tree to track the nesting of the orthogonal QQ factor. The final result is an orthogonal matrix Q=[Q1;Q2;…;QP]Q = [Q_1; Q_2; \ldots; Q_P] distributed in the same block layout as AA and an upper triangular matrix RR copied across all compute nodes. See Figure 8 for a visual representation of the binary tree storage structure for the case P=4P=4. The transposed version of this algorithm is called the Wide-Fat LQ (WFLQ) factorization and has the same tree data storage structure, but every matrix factorization is transposed.

Image not extracted

Figure 8. Parallel TSQR algorithm with 4 compute notes. A binary tree is formed which outlines the communication pattern for calculating the RR factor. At each level, the node with larger ID sends its RR factor to the tree sibling it connects to. The sibling then does a QR factorization with a concatenated pair of child RR factors. This process repeats until the final RR factor is found at the root of the tree stored on processor p=1p=1. We then broadcast this matrix to all other processors. To get the QQ factor, we store the orthogonal QiQ_i for each tree node ii and multiply the parent’s QiQ_i on the right side of the child’s QQ factor, traversing the tree from the root to the leaves. This results in a distributed memory orthogonal matrix Q=[Q1;Q2;Q3;Q4]Q=[Q_1;Q_2;Q_3;Q_4].

Algorithm 3: Parallel Left Orthogonalization

Data: A tensor ff in distributed memory TT format with cores ([C1p],[C2p],…,[Cdp])([C_1^p],[C_2^p],\ldots,[C_d^p]).

Result: A tensor g=fg=f in distributed memory TT format with left orthogonal cores.

Reserve memory for each block DcpD_c^p with sizes of CcpC_c^p.

D1p=C1pD_1^p=C_1^p

for c=1,2,…,d−1c=1,2,\ldots,d-1 do

[Qcp,Rc]=TSQR(V(Dcp))[Q_c^p,R_c]=TSQR(V(D_c^p))

Hc+1p=RcHc(Cc+1p)H_{c+1}^p=R_cH_c(C_{c+1}^p)

Dcp[:]=Qcp[:]⋅HcpD_c^p[:]=Q_c^p[:]\cdot H_c^p

Dc+1p[:]=Hc+1p[:]⋅Hc+1p[:]⋅Hc+1p[:]D_{c+1}^p[:]=H_{c+1}^p[:]\cdot H_{c+1}^p[:]\cdot H_{c+1}^p[:]

end

Set the cores of gg as ([D1p],[D2p],…,[Ddp])([D_1^p],[D_2^p],\ldots,[D_d^p])

Parallel orthogonalization and truncation

We now introduce a parallelization of Algorithms 1 and 2. It can be seen that parallelizing the orthogonalization algorithms is as simple as replacing the QR factorizations with their TSQR variants. However, the truncation is requires a bit of manipulation. In order to parallelize this, we first note the following relationship of the SVD and QR factorizations,

QR=A=UΣVTQR=A=U\Sigma V^{\mathsf{T}}
R=QTUΣVT.R=Q^{\mathsf{T}}U\Sigma V^{\mathsf{T}}.

Thus RR has the same singular values as AA, and so truncating an SVD of RR produces the same approximation

Algorithm 4: Parallel TT Truncation

Data: A tensor ff in distributed memory TT format with cores ([C1p],[C2p],…,[Cdp])([C_1^p], [C_2^p], \ldots, [C_d^p]) and a desired accuracy ε\varepsilon.

Result: A tensor gg so that ∥g−f∥≤ε\lVert g-f\rVert\le\varepsilon in TT format with right orthogonal cores.

Reserve memory for each block DcpD_c^p with sizes of CcpC_c^p.

Set ([C^1p],[C^2p],…,[C^dp])([\widehat{C}_1^p], [\widehat{C}_2^p], \ldots, [\widehat{C}_d^p]) as orthogonal by Alg. 3.

ε^=ε/d−1\widehat{\varepsilon} = \varepsilon/\sqrt{d-1}

Ddp=C^dpD_d^p = \widehat{C}_d^p

for c=d,d−1,…,2c=d,d-1,\ldots,2 do

[Lc,Qcp]=WFLQ(H(Dcp))[L_c,Q_c^p] = WFLQ(H(D_c^p))

[Uc,Σc,VcT]=SVD(Lc,ε^)[U_c,\Sigma_c,V_c^{\mathsf T}] = SVD(L_c,\widehat{\varepsilon}) (Truncated SVD)

Hc−1p=V(C^c−1p)UcΣcH_{c-1}^p = V(\widehat{C}_{c-1}^p)U_c\Sigma_c

Q^cp=VcTQcp\widehat{Q}_c^p = V_c^{\mathsf T}Q_c^p

Dcp[:]=Q^cp[:]D_c^p[:] = \widehat{Q}_c^p[:]

Dc−1p[:]=Hc−1p[:]D_{c-1}^p[:] = H_{c-1}^p[:]

end

Set the cores of gg as ([D1p],[D2p],…,[Ddp])([D_1^p], [D_2^p], \ldots, [D_d^p])

error as truncating AA directly. Since the TSQR algorithm is designed to produce a copy of RR on each compute node, we apply a shared memory SVD redundantly on this copied RR to determine the truncated tensor. This process is formalized in Algorithms 3 and 4. These algorithms are designed so that the only communications required are those that are involved in the computation of the QR or LQ factorizations. Each algorithm is mathematically equivalent to its serial counterpart. The core difference is the use of a superscript p=1,2,…,Pp=1,2,\ldots,P, to denote which matrices take on different values within the different compute nodes. Matrices which are numerically identical across all nodes lack this superscript.

References

References

  1. [1]D. Venturi, The numerical approximation of nonlinear functionals and functional differential equations, Physics Reports 732, 1 (2018).DOI
  2. [2]D. Venturi and A. Dektor, Spectral methods for nonlinear functionals and functional differential equations, Res. Math. Sci. 8, 1 (2021).arxiv.org/abs/2003.14308
  3. [3]E. Hopf, Statistical hydromechanics and functional calculus, J. Rat. Mech. Anal. 1, 87 (1952).DOI
  4. [4]A. S. Monin and A. M. Yaglom, Statistical Fluid Mechanics, Volume II: Mechanics of Turbulence (Dover, 2007).
  5. [5]K. Ohkitani, Study of the Hopf functional equation for turbulence: Duhamel principle and dynamical scaling, Phys. Rev. E 101, 013104 (2020).
  6. [6]G. Rosen, Functional calculus theory for incompressible fluid turbulence, J. Math. Phys. 12, 812 (1971).DOI
  7. [7]N. Vakhania, V. Tarieladze, and S. Chobanyan, Probability distributions on Banach spaces, 1st ed. (Springer, 1987).
  8. [8]C. Foias, Statistical study of Navier-Stokes equations, part I, Rend. Sem. Mat. Univ. Padova 48, 219 (1973).
  9. [9]M. E. Peskin and D. V. Schroeder, An introduction to quantum field theory (CRC Press, 2018).
  10. [10]J. Zinn-Justin, Quantum field theory and critical phenomena, 4th ed. (Oxford Univ. Press, 2002).
  11. [11]P. C. Martin, E. D. Siggia, and H. A. Rose, Statistical dynamics of classical systems, Phys. Rev. A 8, 423 (1973).DOI
  12. [12]R. Phythian, The functional formalism of classical statistical dynamics, J. Phys A: Math. Gen. 10, 777 (1977).DOI
  13. [13]R. V. Jensen, Functional integral approach to classical statistical dynamics, J. Stat. Phys. 25, 183 (1981).
  14. [14]R. Phythian, The operator formalism of classical statistical dynamics, J. Phys A: Math. Gen. 8, 1423 (1975).DOI
  15. [15]B. Jouvet and R. Phythian, Quantum aspects of classical and statistical fields, Phys. Rev. A 19, 1350 (1979).DOI
  16. [16]L. Ruthotto, S. Osher, W. Li, L. Nurbekyan, and S. W. Fung, A machine learning framework for solving high-dimensional mean field game and mean field control problems, PNAS 117, 9183 (2020).DOI
  17. [17]W. E, J. H. Han, and Q. Li, A mean-field optimal control formulation of deep learning, Res. Math. Sci. 6, 10 (2019).
  18. [18]Y. T. Chow, W. Li, S. Osher, and W. Yin, Algorithm for Hamilton–Jacobi equations in density space via a generalized Hopf formula, J. Sci. Comp. 80, 1195 (2019).arxiv.org/abs/1805.01636
  19. [19]W. Gangbo, S. Mayorga, and A. Swiech, Finite dimensional approximations of Hamilton-Jacobi-Bellman equations in spaces of probability measures, SIMA. J. Math. Anal. 53, 1320 (2021).DOI
  20. [20]A. Rodgers, A. Dektor, and D. Venturi, Adaptive integration of nonlinear evolution equations on tensor manifolds, J. Sci. Comput. 92, 1 (2022).arxiv.org/abs/2008.00155
  21. [21]A. Rodgers and D. Venturi, Implicit integration of nonlinear evolution equations on tensor manifolds, J. Sci. Comput 97, 1 (2023).arxiv.org/abs/2207.01962
  22. [22]L. Berselli and S. Spirito, On the existence of Leray-Hopf weak solutions to the Navier-Stokes equations, Fluids 6, 6010042 (2021).DOI
  23. [23]G. Prodi, Un teorema di unicità per le equazioni di Navier–Stokes, Annali di Matematica 48, 173 (1959).DOI
  24. [24]J. Leray, Sur le mouvement d’un liquide visqueux emplissant l’espace, Acta Math. 63, 193 (1934).DOI
  25. [25]E. Fabes, B. Jones, and N. Rivière, The initial value problem for the navier-stokes equations with data in Lp, Arch. Rational Mech. Anal. 45, 222 (1972).DOI
  26. [26]R. Temam, Navier-Stokes equations: theory and numerical analysis (AMS Chelsea Publishing, 1984).
  27. [27]M. J. Vishik and A. V. Fursikov, Mathematical problems of statistical hydromechanics, 2nd ed. (Kluwer Academic Publishers, 1988).DOI
  28. [28]V. I. Gishlarkaeav, Uniqueness of a solution to the Cauchy problem for the Hopf equation in the two-dimensional case, Journal of Mathematical Sciences 169, 64 (2010).
  29. [29]T. Barker, Uniqueness results for weak Leray-Hopf solutions of the Navier-Stokes system with initial values in critical spaces, J. Math. Fluid Mech. 20, 133 (2018).DOI
  30. [30]T. Barker, About local continuity with respect to \(L_2\) initial data for energy solutions of the Navier-Stokes equations, Mathematische Annalen , https://doi.org/10.1007/s00208-020-01988-8 (2020).
  31. [31]T. Kato, Strong \(L^p\) solutions of the Navier-Stokes equation in \(\mathbb {R}^m\), with applications to weak solutions, Math. Z. 187, 471 (1984).
  32. [32]G. P. Galdi, On the relation between very weak and Leray-Hopf solutions to Navier-Stokes equations, Proc. Amer. Math. Soc. 147, 5349 (2019).arxiv.org/abs/1809.03991
  33. [33]S. Dubois, Uniqueness for some Leray–Hopf solutions to the Navier–Stokes, Journal of Differential Equations 189, 99 (2003).DOI
  34. [34]H. Fujita and T. Kato, On the Navier–Stokes initial value problem. I, Arch. Rational Mech. Anal. 16, 269 (1964).
  35. [35]T. Buckmaster and V. Vicol, Nonuniqueness of weak solutions to the Navier–Stokes equation, Annals of Mathematics 189, 101 (2019).arxiv.org/abs/1709.10033
  36. [36]D. Kang and B. Protas, Searching for singularities in Navier–Stokes flows based on the Ladyzhenskaya–Prodi–Serrin conditions, J Nonlinear Sci 32, 1 (2022).DOI
  37. [37]J. Serrin, The initial value problem for the Navier–Stokes equations, Proc. Sympos., Madison, Wis. , 69 (1963).
  38. [38]E. Deriaz and V. Perrier, Divergence-free and curl-free wavelets in two dimensions and three dimensions: application to turbulent flows, Journal of Turbulence 7, 1 (2006).DOI
  39. [39]E. Deriaz and V. Perrier, Direct numerical simulation of turbulence using divergence-free wavelets, Multiscale Model. Simul. 7, 1101 (2008).DOI
  40. [40]E. J. Fuselier and G. B. Wright, A radial basis function method for computing Helmholtz–Hodge decompositions, IMA J. Numer. Anal. 37, 774 (2017).arxiv.org/abs/1502.01575
  41. [41]G. Sacchi-Landriani and H. Vandeven, Polynomial approximation of divergence-free functions, Mathematics of Computation 185, 103 (1989).DOI
  42. [42]K.-J. Engel and R. Nagel, One-parameter semigroups for linear evolution equations, Vol. 194 (Springer, 1999).
  43. [43]D. Guidetti, B. Karasozen, and S. Piskarev, Approximation of abstract differential equations, Journal of Mathematical Sciences 122, 3013 (2004).DOI
  44. [44]A. M. P. Boelens, D. Venturi, and D. M. Tartakovsky, Tensor methods for the Boltzmann-BGK equation, J. Comput. Phys. 421, 109744 (2020).DOI
  45. [45]G. di Marco and L. Pareschi, Numerical methods for kinetic equations, Acta Numerica 23, 369 (2014).
  46. [46]H. J. Bungartz and M. Griebel, Sparse grids, Acta Numerica 13, 147 (2004).
  47. [47]V. Barthelmann, E. Novak, and K. Ritter, High dimensional polynomial interpolation on sparse grids, Advances in Computational Mechanics 12, 273 (2000).DOI
  48. [48]A. Narayan and J. Jakeman, Adaptive Leja sparse grid constructions for stochastic collocation and high-dimensional approximation, SIAM J. Sci. Comput. 36, A2952 (2014).
  49. [49]M. Raissi and G. E. Karniadakis, Hidden physics models: Machine learning of nonlinear partial differential equations, J. Comput. Phys. 357, 125 (2018).DOI
  50. [50]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 (2019).DOI
  51. [51]B. N. Khoromskij, Tensor numerical methods for multi-dimensional PDEs: Theoretical analysis and initial applications, in CEMRACS 2013–modelling and simulation of complex systems: stochastic and deterministic approaches, ESAIM Proc. Surveys, Vol. 48 (EDP Sci., Les Ulis, 2015) pp. 1–28.DOI
  52. [52]M. Bachmayr, R. Schneider, and A. Uschmajew, Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations, Foundations of Computational Mathematics 16, 1423 (2016).DOI
  53. [53]A. M. P. Boelens, D. Venturi, and D. M. Tartakovsky, Parallel tensor methods for high-dimensional linear PDEs, J. Comput. Phys. 375, 519 (2018).DOI
  54. [54]A. Dektor and D. Venturi, Tensor rank reduction via coordinate flows, J. Comp. Phys. 491, 112378 (2023).DOI
  55. [55]A. Dektor and D. Venturi, Coordinate-adaptive integration of PDEs on tensor manifolds, Comm. Appl. Math. Comput. , https://doi.org/10.1007/s42967-024-00335-6 (2024).
  56. [56]H. Cho, D. Venturi, and G. E. Karniadakis, Numerical methods for high-dimensional kinetic equations, in Uncertainty quantification for kinetic and hyperbolic equations, edited by S. Jin and L. Pareschi (Springer, 2017) pp. 93–125.DOI
  57. [57]S. V. Dolgov, TT-GMRES: solution to a linear system in the structured tensor format, Russian Journal of Numerical Analysis and Mathematical Modelling 28, 149 (2013).arxiv.org/abs/1206.5512
  58. [58]G. Beylkin and M. J. Mohlenkamp, Numerical operator calculus in higher dimensions, PNAS 99, 10246 (2002).pubmed.ncbi.nlm.nih.gov/12140360
  59. [59]A. Dektor and D. Venturi, Dynamic tensor approximation of high-dimensional nonlinear PDEs, J. Comput. Phys. 437, 110295 (2021).DOI
  60. [60]D. Bigoni, A. P. Engsig-Karup, and Y. M. Marzouk, Spectral tensor-train decomposition, SIAM J. Sci. Comput. 38, A2405 (2016).
  61. [61]I. V. Oseledets, Tensor-train decomposition, SIAM J. Sci. Comput. 33, 2295– (2011).DOI
  62. [62]R. Schneider and A. Uschmajew, Approximation rates for the hierarchical tensor format in periodic Sobolev spaces, J. Complexity 30, 56 (2014).DOI
  63. [63]L. Grasedyck and C. Löbbert, Distributed hierarchical SVD in the hierarchical Tucker format, Numer. Linear Algebra Appl. 25, e2174 (2018).arxiv.org/abs/1708.03340
  64. [64]A. Etter, Parallel ALS algorithm for solving linear systems in the hierarchical Tucker representation, SIAM J. Sci. Comput. 38, A2585–A2609 (2016).DOI
  65. [65]A. Uschmajew and B. Vandereycken, The geometry of algorithms using hierarchical tensors, Linear Algebra Appl. 439, 133 (2013).DOI
  66. [66]A. Dektor, A. Rodgers, and D. Venturi, Rank-adaptive tensor methods for high-dimensional nonlinear PDEs, J. Sci. Comput. 88, 1 (2021).arxiv.org/abs/2012.05962
  67. [67]M. Griebel and G. Li, On the decay rate of the singular values of bivariate functions, SIAM J. Numer. Anal. 56, 974 (2019).DOI
  68. [68]A. Rodgers and D. Venturi, Stability analysis of hierarchical tensor methods for time-dependent PDEs, J. Comput. Phys. 409, 109341 (2020).DOI
  69. [69]T. Kato, Perturbation theory for linear operators, Classics in Mathematics (Springer-Verlag, Berlin, 1995) pp. xxii+619, reprint of the 1980 edition.
  70. [70]A. Uschmajew and B. Vandereycken, The geometry of algorithms using hierarchical tensors, Linear Algebra Appl. 439, 133 (2013).DOI
  71. [71]D. Kressner, and C. Tobler, Algorithm 941: thucker – a Matlab toolbox for tensors in hierarchical Tucker format, ACM Transactions on Mathematical Software 40, 1 (2014).DOI
  72. [72]H. Cho, D. Venturi, and G. E. Karniadakis, Statistical analysis and simulation of random shocks in Burgers equation, Proc. R. Soc. A 2171, 1 (2014).DOI
  73. [73]D. Venturi, D. M. Tartakovsky, A. M. Tartakovsky, and G. E. Karniadakis, Exact PDF equations and closure approximations for advective-reactive transport, J. Comput. Phys. 243, 323 (2013).DOI
  74. [74]J. S. Hesthaven, Numerical Methods for Conservation Laws: From Analysis to Algorithm, 1st ed. (SIAM, 2018).
  75. [75]P. Lax and B. Wendroff, Systems of conservation laws, Tech. Rep. (Los Alamos National Lab.(LANL), Los Alamos, NM (United States), 1958).
  76. [76]E. Hairer, G. Wanner, and S. P. Nørsett, Solving Ordinary Differential Equations I, Nonstiff Problems, second revised edition. ed., Springer Series in Computational Mathematics,, Vol. 8 (Springer Berlin Heidelberg, Berlin, Heidelberg, 1993).
  77. [77]J. S. Hesthaven, S. Gottlieb, and D. Gottlieb, Spectral methods for time-dependent problems (Cambridge Univ. Press, 2007).DOI
  78. [78]Z. Botev, J. Grotowski, and D. Kroese, Kernel density estimation via diffusion, Annals of Statistics , 2916 (2010).DOI
  79. [79]M. Bhattarai, G. Chennupati, E. Skau, R. Vangara, H. Djidjev, and B. Alexandrov, Distributed non-negative tensor train decomposition, arXiv:2008.01340 , 1 (2020).arxiv.org/abs/2008.01340
  80. [80]L. Einkemmer and I. Joseph, A mass, momentum, and energy conservative dynamical low-rank scheme for the Vlasov equation, J. Comput. Phys. 443, 110495 (2021).DOI
  81. [81]L. Einkemmer and C. Lubich, A low-rank projector-splitting integrator for the Vlasov-Poisson equation, SIAM J. Sci. Comput. 40, B1330 (2018).arxiv.org/abs/1801.01103
  82. [82]L. Einkemmer and C. Lubich, A quasi-conservative dynamical low-rank algorithm for the Vlasov equation, SIAM J. Sci. Comput. 41, B1061 (2019).arxiv.org/abs/1807.02338
  83. [83]I. Oseledets and E. Tyrtyshnikov, TT-cross approximation for multidimensional arrays, Linear Algebra and its Applications 432, 70 (2010).DOI
  84. [84]A. Dektor and D. Venturi, Dynamically orthogonal tensor methods for high-dimensional nonlinear PDEs, J. Comput. Phys. 404, 109125 (2020).DOI
  85. [85]A. Dektor and D. Venturi, Dynamic tensor approximation of high-dimensional nonlinear PDEs, J. Comput. Phys. 437, 110295 (2021).DOI
  86. [86]I. V. Oseledets, Tensor-train decomposition, SIAM Journal on Scientific Computing 33, 2295 (2011), https://doi.org/10.1137/090752286.
  87. [87]H. A. Daas, G. Ballard, and P. Benner, Parallel algorithms for tensor train arithmetic, SIAM J. Sci. Comput. 44, C25 (2022).
  88. [88]J. Demmel, L. Grigori, M. Hoemmen, and J. Langou, Communication-optimal parallel and sequential QR and LU factorizations, SIAM Journal on Scientific Computing 34, A206 (2012).

Paper details

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