A Tensor Decomposition Algorithm for Large ODEs with Conservation Laws

Research output: Contribution to journalArticle

1 Citation (Scopus)
4 Downloads (Pure)

Abstract

We propose an algorithm for solution of high-dimensional evolutionary equations (ODEs and discretized time-dependent PDEs) in the Tensor Train (TT) decomposition, assuming that the solution and the right-hand side of the ODE admit such a decomposition with a low storage. A linear ODE, discretized via one-step or Chebyshev differentiation schemes, turns into a large linear system. The tensor decomposition allows to solve this system for several time points simultaneously using an extension of the Alternating Least Squares algorithm. This method computes a reduced TT model of the solution, but in contrast to traditional offline-online reduction schemes, solving the original large problem is never required. Instead, the method solves a sequence of reduced Galerkin problems, which can be set up efficiently due to the TT decomposition of the right-hand side. The reduced system allows a fast estimation of the time discretization error, and hence adaptation of the time steps. Besides, conservation laws can be preserved exactly in the reduced model by expanding the approximation subspace with the generating vectors of the linear invariants and correction of the Euclidean norm. In numerical experiments with the transport and the chemical master equations, we demonstrate that the new method is faster than traditional time stepping and stochastic simulation algorithms, whereas the invariants are preserved up to the machine precision irrespectively of the TT approximation accuracy.

Original languageEnglish
Pages (from-to)23-38
Number of pages16
JournalComputational Methods in Applied Mathematics
Volume19
Issue number1
Early online date11 Sep 2018
DOIs
Publication statusPublished - 1 Jan 2019

Fingerprint

Tensor Decomposition
Decomposition Algorithm
Conservation Laws
Tensors
Conservation
Decomposition
Tensor
Alternating Least Squares
Euclidean norm
Invariant
Discretization Error
Reduced Model
Least Square Algorithm
Stochastic Simulation
Time Stepping
Time Discretization
Approximation
Master Equation
Chebyshev
Galerkin

Keywords

  • Alternating Iteration
  • Conservation Laws
  • Differential Equations
  • DMRG
  • High-Dimensional Problems
  • Tensor Train Format

ASJC Scopus subject areas

  • Numerical Analysis
  • Computational Mathematics
  • Applied Mathematics

Cite this

A Tensor Decomposition Algorithm for Large ODEs with Conservation Laws. / Dolgov, Sergey V.

In: Computational Methods in Applied Mathematics, Vol. 19, No. 1, 01.01.2019, p. 23-38.

Research output: Contribution to journalArticle

@article{21d9f95bafff4074be171fcd00b117c8,
title = "A Tensor Decomposition Algorithm for Large ODEs with Conservation Laws",
abstract = "We propose an algorithm for solution of high-dimensional evolutionary equations (ODEs and discretized time-dependent PDEs) in the Tensor Train (TT) decomposition, assuming that the solution and the right-hand side of the ODE admit such a decomposition with a low storage. A linear ODE, discretized via one-step or Chebyshev differentiation schemes, turns into a large linear system. The tensor decomposition allows to solve this system for several time points simultaneously using an extension of the Alternating Least Squares algorithm. This method computes a reduced TT model of the solution, but in contrast to traditional offline-online reduction schemes, solving the original large problem is never required. Instead, the method solves a sequence of reduced Galerkin problems, which can be set up efficiently due to the TT decomposition of the right-hand side. The reduced system allows a fast estimation of the time discretization error, and hence adaptation of the time steps. Besides, conservation laws can be preserved exactly in the reduced model by expanding the approximation subspace with the generating vectors of the linear invariants and correction of the Euclidean norm. In numerical experiments with the transport and the chemical master equations, we demonstrate that the new method is faster than traditional time stepping and stochastic simulation algorithms, whereas the invariants are preserved up to the machine precision irrespectively of the TT approximation accuracy.",
keywords = "Alternating Iteration, Conservation Laws, Differential Equations, DMRG, High-Dimensional Problems, Tensor Train Format",
author = "Dolgov, {Sergey V.}",
year = "2019",
month = "1",
day = "1",
doi = "10.1515/cmam-2018-0023",
language = "English",
volume = "19",
pages = "23--38",
journal = "Computational Methods in Applied Mathematics",
issn = "1609-4840",
publisher = "De Gruyter",
number = "1",

}

TY - JOUR

T1 - A Tensor Decomposition Algorithm for Large ODEs with Conservation Laws

AU - Dolgov, Sergey V.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - We propose an algorithm for solution of high-dimensional evolutionary equations (ODEs and discretized time-dependent PDEs) in the Tensor Train (TT) decomposition, assuming that the solution and the right-hand side of the ODE admit such a decomposition with a low storage. A linear ODE, discretized via one-step or Chebyshev differentiation schemes, turns into a large linear system. The tensor decomposition allows to solve this system for several time points simultaneously using an extension of the Alternating Least Squares algorithm. This method computes a reduced TT model of the solution, but in contrast to traditional offline-online reduction schemes, solving the original large problem is never required. Instead, the method solves a sequence of reduced Galerkin problems, which can be set up efficiently due to the TT decomposition of the right-hand side. The reduced system allows a fast estimation of the time discretization error, and hence adaptation of the time steps. Besides, conservation laws can be preserved exactly in the reduced model by expanding the approximation subspace with the generating vectors of the linear invariants and correction of the Euclidean norm. In numerical experiments with the transport and the chemical master equations, we demonstrate that the new method is faster than traditional time stepping and stochastic simulation algorithms, whereas the invariants are preserved up to the machine precision irrespectively of the TT approximation accuracy.

AB - We propose an algorithm for solution of high-dimensional evolutionary equations (ODEs and discretized time-dependent PDEs) in the Tensor Train (TT) decomposition, assuming that the solution and the right-hand side of the ODE admit such a decomposition with a low storage. A linear ODE, discretized via one-step or Chebyshev differentiation schemes, turns into a large linear system. The tensor decomposition allows to solve this system for several time points simultaneously using an extension of the Alternating Least Squares algorithm. This method computes a reduced TT model of the solution, but in contrast to traditional offline-online reduction schemes, solving the original large problem is never required. Instead, the method solves a sequence of reduced Galerkin problems, which can be set up efficiently due to the TT decomposition of the right-hand side. The reduced system allows a fast estimation of the time discretization error, and hence adaptation of the time steps. Besides, conservation laws can be preserved exactly in the reduced model by expanding the approximation subspace with the generating vectors of the linear invariants and correction of the Euclidean norm. In numerical experiments with the transport and the chemical master equations, we demonstrate that the new method is faster than traditional time stepping and stochastic simulation algorithms, whereas the invariants are preserved up to the machine precision irrespectively of the TT approximation accuracy.

KW - Alternating Iteration

KW - Conservation Laws

KW - Differential Equations

KW - DMRG

KW - High-Dimensional Problems

KW - Tensor Train Format

UR - http://www.scopus.com/inward/record.url?scp=85053496467&partnerID=8YFLogxK

U2 - 10.1515/cmam-2018-0023

DO - 10.1515/cmam-2018-0023

M3 - Article

VL - 19

SP - 23

EP - 38

JO - Computational Methods in Applied Mathematics

JF - Computational Methods in Applied Mathematics

SN - 1609-4840

IS - 1

ER -