Robust second-order time integration of tree tensor networks

1 Introduction

• Small singular values of connecting-tensor matricizations can make tree-network low-rank evolution equations ill-conditioned.These singular values correspond to regions of high curvature in the manifold of tree tensor networks.Source: §1 · p. 2
• The parallel and augmented BUG integrators extend second-order time integration to Tucker tensors and tree tensor networks, closing a gap left by matrix and MPS methods.The parallel method evolves all low-rank-factor equations in parallel; the augmented method gives up full parallelism.Source: §1 · pp. 2–3
• The parallel BUG method is rank-adaptive, evolves equations at twice the original rank, and is designed for full parallel execution.Its pre-augmentation encodes half-step information in every differential equation without prohibitive memory and computational costs.Source: §1 · p. 3
• The augmented BUG method conserves norm and energy for Schrödinger equations and dissipates energy for gradient flows up to truncation tolerance.It gives up full parallelism in exchange for these properties.Source: §1 · p. 3
• Numerical experiments evaluate the integrators on radiative transfer and quantum spin systems.The paper presents these experiments as validation of its theoretical findings.Source: §1 · p. 3

2 Recap: The second-order parallel basis-update & Galerkin integrator

• Pre-augmentation uses the initial bases and right-hand side to build enlarged bases before parallel evolution of the K, L, and core equations.The K and L steps each evolve an m-by-2r or n-by-2r equation and construct enlarged orthonormal bases; the core equation is 2r-by-2r.Source: §2 · pp. 3–4
• The resulting bases are augmented from the evolved K and L factors, with zero columns used when the resulting range has insufficient rank, then truncated to tolerance ϑ.The basis construction uses QR decomposition, and the final truncation is tolerance-controlled.Source: §2 · p. 4
• The parallel integrator is second order and rank-adaptive, evolving all differential equations forward in time.It solves rank-2r equations rather than the sequential 4r coefficient updates of the midpoint BUG integrator, and evolves all equations in parallel.Source: §2 · p. 4
• The robust error bound assumes F is Lipschitz continuous and bounded, with normal components at rank-r solutions bounded by ε_r.The bound's constants are independent of small singular values; its error also accounts for averaged normal components across numerical ranks.Source: §2 · pp. 4–5

3.1 Formulation of the algorithm

• The Tucker algorithm precomputes augmented bases, evolves the mode-wise K-step and core-tensor differential equations in parallel, then augments and truncates sequentially.The time evolution is parallel, while pre-augmentation, augmentation, and truncation remain sequential.Source: §3.1 · pp. 5–6

3.2 Robust second-order error bound

• Under assumptions A1–A3, the integrator has a global second-order error bound whose constants are independent of small singular values of connecting-tensor matricizations.The bound applies with step size h and rank-truncation tolerance ϑ.Source: §3.2 · pp. 7–8
• The pre-augmented basis approximates the half-step solution with error O(h^2 + hε̄_r), a key ingredient in the second-order analysis.The proof then bounds projection of the full solution onto the updated basis and the difference between projected full dynamics and the integrator.Source: §3.2 · pp. 8–9
• The error-bound constants depend only on bounds for F and its Lipschitz constant, third derivatives of the exact solution, and the timestep size.The supplied passage does not specify the bound’s order or state its dependence on singular values.Source: §3.2 · p. 11
• The bases generated in the Ki-steps suffice to approximate the solution at the next timestep; the passage then turns to core-tensor coefficient approximation.It identifies the optimal coefficients as bCA := A(t1)X_i and says they can be distinguished in several blocks, without describing those blocks here.Source: §3.2 · p. 12

• The core tensor is shown to be approximated sufficiently accurately for index sets J with at least two elements.Source: bCA X · p. 12
• The proposed tensor integrator has a robust error bound under the stated assumptions.The proof bounds the distance between projected full dynamics and the parallel integrator; the bound's constants depend on the Lipschitz constant and bound of F, a third-derivative bound, and the timestep upper bound.Source: bCA X · pp. 13–14
• The local error bound contains h^3 terms and terms involving ε_r and ε̄_r.Source: bCA X · p. 14
• The analysis improves the first-order parallel BUG integrator by replacing its explicit-Euler-based block update.That update can impair accuracy and stability even when K_i and C̄ use implicit or higher-order methods, and it requires additional right-hand-side evaluations; the replacement decouples the update from explicit Euler and reduces computational costs.Source: bCA X · p. 14

4.1 Formulation of the algorithm

• The Tucker step pre-augments bases, evolves the Ki equations, integrates a 4r1×···×4rd tensor equation, and truncates to tolerance ϑ.The full 4r1×···×4rd tensor step avoids a separate augmentation step but is significantly more expensive than the 2r1×···×2rd equation in the parallel version.Source: §4.1 · p. 15

4.2 Robust error bound

• Theorem 4.1 gives a second-order error bound whose constants are independent of small singular values of connecting-tensor matricizations.The proof extends the bound through local-error control and propagation by the exact flow.Source: §4.2 · pp. 15–16
• The error-bound argument also gives a strategy for higher-order augmented BUG integrators, using μp and order-p derivatives of R(t0).The remark states that the proof can be extended to arbitrary order.Source: §4.2 · p. 17

Norm conservation

• Under the stated condition on F, each step preserves norm, while truncation yields near-conservation within a multiple of ϑ.The proof relies on an orthogonal basis and a Galerkin update of the connecting tensor.Source: Norm conservation · p. 17, §4.3 · p. 17
• For a linear self-adjoint Hamiltonian, the integrator preserves energy stepwise, with truncation giving near-conservation up to a multiple of ϑ.The energy is defined as E(Y) = ⟨Y, H[Y]⟩.Source: Norm conservation · pp. 17–18

Energy decay for gradient systems

• For gradient systems, the second-order augmented BUG integrator diminishes energy for every step size h > 0.The stated conclusion is qualified by the truncation analysis.Source: Energy decay for gradient systems · p. 18

5 Second-Order Tree Tensor Network Integrators

• Tree tensor networks provide a hierarchical, data-sparse format for approximating high-dimensional tensors.Their hierarchy is encoded by a tree whose leaves may be unequal.Source: §5 · p. 18
• A tree tensor network is recursively built from leaf basis matrices and connecting tensors associated with subtrees.The definition assumes full multilinear rank for the connecting tensors and defines orthonormality through orthonormal columns of subtree bases.Source: §5 · p. 19
• Tree tensor networks contain tensor trains, also called matrix product states, and do not allow loops.Binary trees are also studied as hierarchical Tucker tensors.Source: §5 · p. 20

5.1 Second-order parallel TTN integrator

• The tree-network formulation falls back to the Tucker integrator in the Tucker case and begins with sequential basis augmentation from leaves to root.The section introduces this construction for a fixed tree and corresponding initial network.Source: §5.1 · p. 20, §1 · p. 21

1. Pre-augmentation

• The parallel BUG workflow precomputes reduced data, evolves the effective equations in parallel, augments the network sequentially, and truncates it to the requested ranks.The pre-augmentation and augmentation sweeps proceed through tree levels; operations at a given level can be parallelized.Source: §1 · p. 21, §5.1.1 · p. 21

5.1.2 Augmented restriction to the subtrees: Q0 τi, S0 τi and bQ0

• For each subtree, pre-augmentation constructs augmented bases and reduced functions, including an augmented 0-mode for the parent environment.That 0-mode dimension distinguishes the augmented reduced functions from the reduced functions.Source: §5.1.2 · pp. 22–23

5.1.3 Parallel time integration

• All basis matrices and core tensors are evolved fully in parallel, using effective equations whose dimensions are doubled from the original tree ranks.The procedure describes separate evolutions for leaves and core tensors.Source: §5.1.3 · pp. 24–25

5.1.4 Augmentation of core tensors

• After time evolution, core tensors are augmented recursively from the leaves to the root, with non-root nodes also augmenting the 0-mode.The resulting network is fully augmented before truncation.Source: §5.1.4 · pp. 25–26

5.1.5 Truncation

• A standard truncation is performed on the tree tensor network using a user-defined tolerance ϑ, resulting in a tree tensor network.A detailed explanation is given in [12, Algorithm 7].Source: §5.1.5 · p. 26

5.2 Second-order augmented BUG for tree tensor networks

• The augmented BUG variant pre-augments the network, updates leaves, updates core tensors recursively from the lowest level to the root, and truncates.Its core update uses bases spanning the ranges of the updated and previous core tensors.Source: §5.2 · p. 27

5.3 Robust error bound

• Under assumptions A1–A3, both tree-network integrators have a robust second-order error bound with constants independent of small singular values of connecting-tensor matricizations.The assumptions include bounded Lipschitz dynamics, a small tangent-space remainder, and bounded initial error.Source: §5.3 · pp. 27–28
• The augmented BUG variant preserves norm and energy for Schrödinger equations and diminishes energy in gradient systems, up to truncation tolerance.The tree-network proofs follow the arguments used for the Tucker case.Source: §5.3 · pp. 27–28

6.1 Uncertain radiative transfer

• The radiative-transfer benchmark introduces uncertain scattering coefficients and compares the integrators with a full-rank reference solution.The test uses σs(ξ) = 5 + 4 · ξ and 100 degrees of freedom in each of space, time, and direction.Source: §6.1 · pp. 28–29

6.2 Schr¨odinger equation for quantum spin systems

• Both integrators show second-order convergence for uncertain radiative transfer and for the quantum-spin tree-network test.The radiative-transfer experiment tracks expected-value, variance, and full-solution errors; the quantum-spin test compares both methods with the exact solution.Source: §6.1 · p. 29, §6.2 · p. 30, Figure 1 · p. 30
• The augmented BUG integrator appears to have a smaller error constant than parallel BUG in the quantum-spin test.At the smallest step sizes, both methods saturate at the projection error with maximal rank 10.Source: §6.2 · p. 30
• With truncation tolerance ϑ = 10−14, augmented BUG preserves norm and energy, while parallel BUG deviations are 10−11 for norm and 10−7 for energy.The parallel method does not have these preservation properties by construction because its augmented connecting tensor is assembled from approximated blocks.Source: §6.2 · p. 31