An improved numerical method for balanced truncation for symmetric second-order systems

We consider balanced truncation model order reduction for symmetric second-order systems. The occurring large-scale generalized and structured Lyapunov equations are solved with a specially adapted low-rank alternating directions implicit (ADI) type method. Stopping criteria for this iteration are investigated, and a new result concerning the Lyapunov residual within the low-rank ADI method is established. We also propose a goal-oriented stopping criterion which tries to incorporate the balanced truncation approach already during the ADI iteration. The model reduction approach using the ADI method with different stopping criteria is evaluated on several test systems.     

Efficient solution of large scale Lyapunov and Riccati equations arising in model order reduction problems

Model order reduction of large–scale linear time–invariant systems is an omnipresent task in control and simulation of complex dynamical processes. The solution of large scale Lyapunov and Riccati equations is a major task, e.g., in balanced truncation and related model order reduction methods, in particular when applied to semi–discretized partial differential equations constraint control problems. The software package LyaPack has shown to be a valuable tool in the task of solving these equations since its introduction in 2000. Here we want to discuss recent improvements and extensions of the underlying algorithms and their implementation. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the numerical solution of large-scale sparse discrete-time Riccati equations

We discuss the numerical solution of large-scale discrete-time algebraic Riccati equations (DAREs) as they arise, e.g., in fully discretized linear-quadratic optimal control problems for parabolic partial differential equations (PDEs). We employ variants of Newton??s method that allow to compute an approximate low-rank factor of the solution of the DARE. The principal computation in the Newton iteration is the numerical solution of a Stein (aka discrete Lyapunov) equation in each step. For this purpose, we present a low-rank Smith method as well as a low-rank alternating-direction-implicit (ADI) iteration to compute low-rank approximations to solutions of Stein equations arising in this context. Numerical results are given to verify the efficiency and accuracy of the proposed algorithms.     

Solving Differential Matrix Equations using Parareal

Differential matrix equations appear in many applications like optimal control of partial differential equations, balanced truncation model order reduction of linear time varying systems and many more. Here, we will focus on differential Riccati equations (DRE). Solving such matrix-valued ordinary differential equations (ODE) is a highly time consuming process. We present a Parareal based algorithm applied to Rosenbrock methods for the solution of the matrix-valued differential Riccati equations. Considering problems of moderate size, direct matrix equation solvers for the solution of the algebraic Lyapunov equations arising inside the time intgration methods are used. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A projector-splitting integrator for dynamical low-rank approximation

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 explicit, 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.     

An LDLT factorization based ADI algorithm for solving large-scale differential matrix equations

Large-scale differential matrix equations appear in many applications like optimal control of partial differential equations, balanced truncation model order reduction of linear time varying systems etc. Here, we will focus on matrix Riccati differential equations (RDE). Solving such matrix valued ordinary differential equations (ODE) is a highly storage and time consuming process. Therefore, it is necessary to develop efficient solution strategies minimizing both. We present an LDL^T factorization based ADI method for solving algebraic Lyapunov equations (ALE) arising in the innermost iteration during the application of Rosenbrock ODE solvers to RDEs. We show that the LDL^T-type decomposition avoids complex arithmetic, as well as cancellation effects arising from indefinite right hand sides of the ALEs appearing in the classic ZZ^T based approach. Additionally, a certain number of linear system solves can be saved within the ADI algorithm by reducing the number of column blocks in the right hand sides while the full accuracy of the standard low-rank ADI is preserved. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Low rank methods for a class of generalized Lyapunov equations and related issues

In this paper, we study possible low rank solution methods for generalized Lyapunov equations arising in bilinear and stochastic control. We show that under certain assumptions one can expect a strong singular value decay in the solution matrix allowing for low rank approximations. Since the theoretical tools strongly make use of a connection to the standard linear Lyapunov equation, we can even extend the result to the $d$ -dimensional case described by a tensorized linear system of equations. We further provide some reasonable extensions of some of the most frequently used linear low rank solution techniques such as the alternating directions implicit (ADI) iteration and the Krylov-Plus-Inverted-Krylov (K-PIK) method. By means of some standard numerical examples used in the area of bilinear model order reduction, we will show the efficiency of the new methods.     

A preconditioned low‐rank CG method for parameter‐dependent Lyapunov matrix equations

This paper is concerned with the numerical solution of symmetric large‐scale Lyapunov equations with low‐rank right‐hand sides and coefficient matrices depending on a parameter. Specifically, we consider the situation when the parameter dependence is sufficiently smooth, and the aim is to compute solutions for many different parameter samples. On the basis of existing results for Lyapunov equations and parameter‐dependent linear systems, we prove that the tensor containing all solution samples typically allows for an excellent low multilinear rank approximation. Stacking all sampled equations into one huge linear system, this fact can be exploited by combining the preconditioned CG method with low‐rank truncation. Our approach is flexible enough to allow for a variety of preconditioners based, for example, on the sign function iteration or the alternating direction implicit method. Copyright © 2013 John Wiley & Sons, Ltd.     

Balanced truncation for linear switched systems

We propose a model order reduction approach for balanced truncation of linear switched systems. Such systems switch among a finite number of linear subsystems or modes. We compute pairs of controllability and observability Gramians corresponding to each active discrete mode by solving systems of coupled Lyapunov equations. Depending on the type, each such Gramian corresponds to the energy associated to all possible switching scenarios that start or, respectively end, in a particular operational mode. In order to guarantee that hard to control and hard to observe states are simultaneously eliminated, we construct a transformed system, whose Gramians are equal and diagonal. Then, by truncation, directly construct reduced order models. One can show that these models preserve some properties of the original model, such as stability and that it is possible to obtain error bounds relating the observed output, the control input and the entries of the diagonal Gramians.     

Tensor Networks and Hierarchical Tensors for the Solution of High-Dimensional Partial Differential Equations

Hierarchical tensors can be regarded as a generalisation, preserving many crucial features, of the singular value decomposition to higher-order tensors. For a given tensor product space, a recursive decomposition of the set of coordinates into a dimension tree gives a hierarchy of nested subspaces and corresponding nested bases. The dimensions of these subspaces yield a notion of multilinear rank. This rank tuple, as well as quasi-optimal low-rank approximations by rank truncation, can be obtained by a hierarchical singular value decomposition. For fixed multilinear ranks, the storage and operation complexity of these hierarchical representations scale only linearly in the order of the tensor. As in the matrix case, the set of hierarchical tensors of a given multilinear rank is not a convex set, but forms an open smooth manifold. A number of techniques for the computation of hierarchical low-rank approximations have been developed, including local optimisation techniques on Riemannian manifolds as well as truncated iteration methods, which can be applied for solving high-dimensional partial differential equations. This article gives a survey of these developments. We also discuss applications to problems in uncertainty quantification, to the solution of the electronic Schrödinger equation in the strongly correlated regime, and to the computation of metastable states in molecular dynamics.     

Hermitian spectral pseudoinversion and its applications

The present paper is devoted to the Hermitian spectral pseudoinversion and its applications to analysis, the solution and reduction of Hermitian differential-algebraic systems. New explicit formulas for the solutions of such systems and the solutions of related generalized Lyapunov equations are proposed. Attainable upper bounds for the norms of the solutions are obtained. A realization of the balanced truncation method not requiring computations involving projections onto deflating subspaces is proposed.     

Adaptive high-order splitting schemes for large-scale differential Riccati equations

We consider high-order splitting schemes for large-scale differential Riccati equations. Such equations arise in many different areas and are especially important within the field of optimal control. In the large-scale case, it is critical to employ structural properties of the matrix-valued solution, or the computational cost and storage requirements become infeasible. Our main contribution is therefore to formulate these high-order splitting schemes in an efficient way by utilizing a low-rank factorization. Previous results indicated that this was impossible for methods of order higher than 2, but our new approach overcomes these difficulties. In addition, we demonstrate that the proposed methods contain natural embedded error estimates. These may be used, e.g., for time step adaptivity, and our numerical experiments in this direction show promising results.     

Model reduction for optimal control problems in field-flow fractionation

We discuss the application of model order reduction to optimal control problems governed by coupled systems of the Stokes-Brinkman and advection-diffusion equations. Such problems arise in field-flow fractionation processes for the efficient and fast separation of particles of different size in microfluidic flows. Our approach is based on a combination of balanced truncation and tangential interpolation for model reduction of the semidiscretized optimality system. Numerical results demonstrate the properties of this approach. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A preconditioned block Arnoldi method for large scale Lyapunov and algebraic Riccati equations

In the present paper, we propose a preconditioned Newton–Block Arnoldi method for solving large continuous time algebraic Riccati equations. Such equations appear in control theory, model reduction, circuit simulation amongst other problems. At each step of the Newton process, we solve a large Lyapunov matrix equation with a low rank right hand side. These equations are solved by using the block Arnoldi process associated with a preconditioner based on the alternating direction implicit iteration method. We give some theoretical results and report numerical tests to show the effectiveness of the proposed approach.     

Balanced POD for model reduction of linear PDE systems: convergence theory

We consider convergence analysis for a model reduction algorithm for a class of linear infinite dimensional systems. The algorithm computes an approximate balanced truncation of the system using solution snapshots of specific linear infinite dimensional differential equations. The algorithm is related to the proper orthogonal decomposition, and it was first proposed for systems of ordinary differential equations by Rowley (Int. J. Bifurc. Chaos Appl. Sci. Eng. 15(3):997?C1013, 2005). For the convergence analysis, we consider the algorithm in terms of the Hankel operator of the system, rather than the product of the system Gramians as originally proposed by Rowley. For exponentially stable systems with bounded finite rank input and output operators, we prove that the balanced realization can be expressed in terms of balancing modes, which are related to the Hankel operator. The balancing modes are required to be smooth, and this can cause computational difficulties for PDE systems. We show how this smoothness requirement can be lessened for parabolic systems, and we also propose a variation of the algorithm that avoids the smoothness requirement for general systems. We prove entrywise convergence of the matrices in the approximate reduced order models in both cases, and present numerical results for two example PDE systems.     

Symmetric Positivity Preserving Balanced Truncation

We consider positivity preserving model order reduction of SISO linear systems. Whereas well-established model reduction methods usually do not result in a positive approximation, we show that a symmetry characterization of balanced truncation can be used to preserve positivity after performing balanced truncation. As a consequence, the method is independent of the initial realization and always returns a symmetric reduced model. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)