Christian Lubich

Christian Lubich, Ivan Oseledets

The dynamical low-rank approximation of time-dependent matrices is a low-rank factorization updating technique. It leads to differential equations for factors of the matrices, which need to be solved numerically. We propose and analyze a fully ex- plicit, computationally inexpensive integrator that is based on splitting the orthogonal projector onto the tangent space of the low-rank manifold. As is shown by theory and illustrated by numerical experiments, the integrator enjoys robustness properties that are not shared by any standard numerical integrator. This robustness can be exploited to change the rank adaptively. Another application is in optimization algorithms for low-rank matrices where truncation back to the given low rank can be done efficiently by applying a step of the integrator proposed here.

Christian Lubich, Ivan Oseledets, Bart Vandereycken

A robust and efficient time integrator for dynamical tensor approximation in the tensor train or matrix product state format is presented. The method is based on splitting the projector onto the tangent space of the tensor manifold. The algorithm can be used for updating time-dependent tensors in the given data-sparse tensor train / matrix product state format and for computing an approximate solution to high-dimensional tensor differential equations within this data-sparse format. The formulation, implementation and theoretical properties of the proposed integrator are studied, and numerical experiments with problems from quantum molecular dynamics and with iterative processes in the tensor train format are included.

Lukas Einkemmer, Christian Lubich

Many problems encountered in plasma physics require a description by kinetic equations, which are posed in an up to six-dimensional phase space. A direct discretization of this phase space, often called the Eulerian approach, has many advantages but is extremely expensive from a computational point of view. In the present paper we propose a dynamical low-rank approximation to the Vlasov--Poisson equation, with time integration by a particular splitting method. This approximation is derived by constraining the dynamics to a manifold of low-rank functions via a tangent space projection and by splitting this projection into the subprojections from which it is built. This reduces a time step for the six- (or four-) dimensional Vlasov--Poisson equation to solving two systems of three- (or two-) dimensional advection equations over the time step, once in the position variables and once in the velocity variables, where the size of each system of advection equations is equal to the chosen rank. By a hierarchical dynamical low-rank approximation, a time step for the Vlasov--Poisson equation can be further reduced to a set of six (or four) systems of one-dimensional advection equations, where the size of each system of advection equations is still equal to the rank. The resulting systems of advection equations can then be solved by standard techniques such as semi-Lagrangian or spectral methods. Numerical simulations in two and four dimensions for linear Landau damping, for a two-stream instability and for a plasma echo problem highlight the favorable behavior of this numerical method and show that the proposed algorithm is able to drastically reduce the required computational effort.

Georgios Akrivis, Buyang Li, Christian Lubich

We analyze fully implicit and linearly implicit backward difference formula (BDF) methods for quasilinear parabolic equations, without making any assumptions on the growth or decay of the coefficient functions. We combine maximal parabolic regularity and energy estimates to derive optimal-order error bounds for the time-discrete approximation to the solution and its gradient in the maximum norm and energy norm.

Balázs Kovács, Buyang Li, Christian Lubich

It is shown that for a parabolic problem with maximal $L^p$-regularity (for $1<p<\infty$), the time discretization by a linear multistep method or Runge--Kutta method has maximal $\ell^p$-regularity uniformly in the stepsize if the method is A-stable (and satisfies minor additional conditions). In particular, the implicit Euler method, the Crank-Nicolson method, the second-order backward difference formula (BDF), and the Radau IIA and Gauss Runge--Kutta methods of all orders preserve maximal regularity. The proof uses Weis' characterization of maximal $L^p$-regularity in terms of $R$-boundedness of the resolvent, a discrete operator-valued Fourier multiplier theorem by Blunck, and generating function techniques that have been familiar in the stability analysis of time discretization methods since the work of Dahlquist. The A($α$)-stable higher-order BDF methods have maximal $\ell^p$-regularity under an $R$-boundedness condition in a larger sector. As an illustration of the use of maximal regularity in the error analysis of discretized nonlinear parabolic equations, it is shown how error bounds are obtained without using any growth condition on the nonlinearity or for nonlinearities having singularities.

Balázs Kovács, Buyang Li, Christian Lubich et al.

For a parabolic surface partial differential equation coupled to surface evolution, convergence of the spatial semidiscretization is studied in this paper. The velocity of the evolving surface is not given explicitly, but depends on the solution of the parabolic equation on the surface. Various velocity laws are considered: elliptic regularization of a direct pointwise coupling, a regularized mean curvature flow and a dynamic velocity law. A novel stability and convergence analysis for evolving surface finite elements for the coupled problem of surface diffusion and surface evolution is developed. The stability analysis works with the matrix-vector formulation of the method and does not use geometric arguments. The geometry enters only into the consistency estimates. Numerical experiments complement the theoretical results.

Balázs Kovács, Christian Lubich

Space and time discretizations of parabolic differential equations with dynamic boundary conditions are studied in a weak formulation that fits into the standard abstract formulation of parabolic problems, just that the usual L^2(Ω) inner product is replaced by an L^2(Ω) \oplus L^2(Γ) inner product. The class of parabolic equations considered includes linear problems with time- and space-dependent coefficients and semilinear problems such as reaction-diffusion on a surface coupled to diffusion in the bulk. The spatial discretization by finite elements is studied in the proposed framework, with particular attention to the error analysis of the Ritz map for the elliptic bilinear form in relation to the inner product, both of which contain boundary integrals. The error analysis is done for both polygonal and smooth domains. We further consider mass lumping, which enables us to use exponential integrators and bulk-surface splitting for time integration.

Lukas Einkemmer, Christian Lubich

Numerical methods that approximate the solution of the Vlasov-Poisson equation by a low-rank representation have been considered recently. These methods can be extremely effective from a computational point of view, but contrary to most Eulerian Vlasov solvers, they do not conserve mass and momentum, neither globally nor in respecting the corresponding local conservation laws. This can be a significant limitation for intermediate and long time integration. In this paper we propose a numerical algorithm that overcomes some of these difficulties and demonstrate its utility by presenting numerical simulations.

David Cohen, Ludwig Gauckler, Ernst Hairer et al.

For trigonometric and modified trigonometric integrators applied to oscillatory Hamiltonian differential equations with one or several constant high frequencies, near-conservation of the total and oscillatory energies are shown over time scales that cover arbitrary negative powers of the step size. This requires non-resonance conditions between the step size and the frequencies, but in contrast to previous results the results do not require any non-resonance conditions among the frequencies. The proof uses modulated Fourier expansions with appropriately modified frequencies.

Peer C. Kunstmann, Buyang Li, Christian Lubich

For a large class of fully nonlinear parabolic equations, which include gradient flows for energy functionals that depend on the solution gradient, the semidiscretization in time by implicit Runge-Kutta methods such as the Radau IIA methods of arbitrary order is studied. Error bounds are obtained in the $W^{1,\infty}$ norm uniformly on bounded time intervals and, with an improved approximation order, in the parabolic energy norm. The proofs rely on discrete maximal parabolic regularity. This is used to obtain $W^{1,\infty}$ estimates, which are the key to the numerical analysis of these problems.

Ludwig Gauckler, Ernst Hairer, Christian Lubich

Geometric aspects play an important role in the construction and analysis of structure-preserving numerical methods for a wide variety of ordinary and partial differential equations. Here we review the development and theory of symplectic integrators for Hamiltonian ordinary and partial differential equations, of dynamical low-rank approximation of time-dependent large matrices and tensors, and its use in numerical integrators for Hamiltonian tensor network approximations in quantum dynamics.

Balázs Kovács, Christian Lubich

Semidiscretization in time is studied for a class of quasi-linear evolution equations in a framework due to Kato, which applies to symmetric first-order hyperbolic systems and to a variety of fluid and wave equations. In the regime where the solution is suffciently regular, we show stability and optimal-order convergence of the linearly implicit and fully implicit midpoint rules and of higher-order implicit Runge{Kutta methods that are algebraically stable and coercive, such as the collocation methods at Gauss nodes.

Lehel Banjai, Christian Lubich

A coercivity property of temporal convolution operators is an essential tool in the analysis of time-dependent boundary integral equations and their space and time discretisations. It is known that this coercivity property is inherited by convolution quadrature time discretisation based on A-stable multistep methods, which are of order at most two. Here we study the question as to which Runge--Kutta-based convolution quadrature methods inherit the convolution coercivity property. It is shown that this holds without any restriction for the third-order Radau IIA method, and on permitting a shift in the Laplace domain variable, this holds for all algebraically stable Runge--Kutta methods and hence for methods of arbitrary order. As an illustration, the discrete convolution coercivity is used to analyse the stability and convergence properties of the time discretisation of a non-linear boundary integral equation that originates from a non-linear scattering problem for the linear wave equation. Numerical experiments illustrate the error behaviour of the Runge--Kutta convolution quadrature time discretisation.

Balázs Kovács, Christian Lubich

Stability and convergence of full discretizations of various surface evolution equations are studied in this paper. The proposed discretization combines a higher-order evolving-surface finite element method (ESFEM) for space discretization with higher-order linearly implicit backward difference formulae (BDF) for time discretization. The stability of the full discretization is studied in the matrix--vector formulation of the numerical method. The geometry of the problem enters into the bounds of the consistency errors, but does not enter into the proof of stability. Numerical examples illustrate the convergence behaviour of the full discretization.

Christian Lubich, Daniel Weiss

This paper deals with the numerical integration of Hamiltonian systems in which a stiff anharmonic potential causes highly oscillatory solution behavior with solution-dependent frequencies. The impulse method, which uses micro- and macro-steps for the integration of fast and slow parts, respectively, does not work satisfactorily on such problems. Here it is shown that variants of the impulse method with suitable projection preserve the actions as adiabatic invariants and yield accurate approximations, with macro-stepsizes that are not restricted by the stiffness parameter.

Eleonora Andreotti, Dominik Edelmann, Nicola Guglielmi et al.

Given a connected undirected weighted graph, we are concerned with problems related to partitioning the graph. First of all we look for the closest disconnected graph (the minimum cut problem), here with respect to the Euclidean norm. We are interested in the case of constrained minimum cut problems, where constraints include cardinality or membership requirements, which leads to NP-hard combinatorial optimization problems. Furthermore, we are interested in ambiguity issues, that is in the robustness of clustering algorithms that are based on Fiedler spectral partitioning. The above-mentioned problems are restated as matrix nearness problems for the weight matrix of the graph. A key element in the solution of these matrix nearness problems is the use of a constrained gradient system of matrix differential equations.

Michael Feischl, Caroline Lasser, Christian Lubich et al.

This paper studies the numerical approximation of evolution equations by nonlinear parametrizations $u(t)=Φ(\param(t))$ with time-dependent parameters $\param(t)$, which are to be determined in the computation. The motivation comes from approximations in quantum dynamics by multiple Gaussians and approximations of various dynamical problems by tensor networks and neural networks. In all these cases, the parametrization is typically irregular: the derivative $Φ'(\param)$ can have arbitrarily small singular values and may have varying rank. We derive approximation results for a regularized approach in the time-continuous case as well as in time-discretized cases. For the latter, there is a nontrivial interplay between the regularization parameter and the time stepsize, depending also on the defect size and local bounds of the second derivative of the parametrization map $Φ$. When this is appropriately taken into account, the approach can be successfully applied in irregular situations, even though it runs counter to the basic principle in numerical analysis to avoid solving ill-posed subproblems when aiming for a stable algorithm. The paper also includes two theoretical case studies: regularized parametric steepest descent for optimization and regularized parametric Strang splitting for the time-dependent Schrödinger equation. Numerical experiments with sums of Gaussians for approximating quantum dynamics and with neural networks for approximating the flow map of a system of ordinary differential equations illustrate and complement the theoretical results.

Christian Lubich, Jörg Nick

Evolutionary deep neural networks have emerged as a rapidly growing field of research. This paper studies numerical integrators for such and other classes of nonlinear parametrizations $ u(t) = Φ(θ(t)) $, where the evolving parameters $θ(t)$ are to be computed. The primary focus is on tackling the challenges posed by the combination of stiff evolution problems and irregular parametrizations, which typically arise with neural networks, tensor networks, flocks of evolving Gaussians, and in further cases of overparametrization. We propose and analyse regularized parametric versions of the implicit Euler method and higher-order implicit Runge--Kutta methods for the time integration of the parameters in nonlinear approximations to evolutionary partial differential equations and large systems of stiff ordinary differential equations. At each time step, an ill-conditioned nonlinear optimization problem is solved approximately with a few regularized Gauss--Newton iterations. Error bounds for the resulting parametric integrator are derived by relating the computationally accessible Gauss--Newton iteration for the parameters to the computationally inaccessible Newton iteration for the underlying non-parametric time integration scheme. The theoretical findings are supported by numerical experiments that are designed to show key properties of the proposed parametric integrators.

Christian Lubich, Bart Vandereycken, Hanna Walach

Dynamical low-rank approximation in the Tucker tensor format of given large time-dependent tensors and of tensor differential equations is the subject of this paper. In particular, a discrete time integration method for rank-constrained Tucker tensors is presented and analyzed. It extends the known projector-splitting integrator for dynamical low-rank approximation of matrices to Tucker tensors and is shown to inherit the same favorable properties. The integrator is based on iteratively applying the matrix projector-splitting integrator to tensor unfoldings but with inexact solution in a substep. It has the property that it reconstructs time-dependent Tucker tensors of the given rank exactly. The integrator is also shown to be robust to the presence of small singular values in the tensor unfoldings. Numerical examples with problems from quantum dynamics and tensor optimization methods illustrate our theoretical results.

María López-Fernández, Christian Lubich, Achim Schädle

To approximate convolutions which occur in evolution equations with memory terms, a variable-stepsize algorithm is presented for which advancing N steps requires only O(N log(N)) operations and O(log(N)) active memory, in place of O(N^2) operations and O(N) memory for a direct implementation. A basic feature of the fast algorithm is the reduction, via contour integral representations, to differential equations which are solved numerically with adaptive step sizes. Rather than the kernel itself, its Laplace transform is used in the algorithm. The algorithm is illustrated on three examples: a blow-up example originating from a Schrödinger equation with concentrated nonlinearity, chemical reactions with inhibited diffusion, and viscoelasticity with a fractional order constitutive law.

Achim Schädle, María López-Fernández, Christian Lubich

We give an algorithm to compute $N$ steps of a convolution quadrature approximation to a continuous temporal convolution using only $O(N \log N)$ multiplications and $O(\log N)$ active memory. The method does not require evaluations of the convolution kernel, but instead $O(\log N)$ evaluations of its Laplace transform, which is assumed sectorial. The algorithm can be used for the stable numerical solution with quasi-optimal complexity of linear and nonlinear integral and integro-differential equations of convolution type. In a numerical example we apply it to solve a subdiffusion equation with transparent boundary conditions.

María López-Fernández, Christian Lubich, Cesar Palencia et al.

The result after $N$ steps of an implicit Runge-Kutta time discretization of an inhomogeneous linear parabolic differential equation is computed, up to accuracy $ε$, by solving only $$O\Big(\log N \log \frac1ε\Big) $$ linear systems of equations. We derive, analyse, and numerically illustrate this fast algorithm.