List of Abstracts
pdf file containing all abstracts.Athanasios C. Antoulas: Parametric model reduction
Rice University, USAWe present an approach to model reduction of systems depending on one parameter. It is based on a generalization of the Loewner matrix for 2-variate functions. The key is the establishment of a method which guarantees a trade-off between model complexity (in both variables) and accuracy of fit.
Sebastian Birk: A deflated conjugate gradient method for multiple right hand sides and multiple shifts
Bergische Universität Wuppertal, GermanyComputations in QCD simulations often require the solution of linear systems that only differ by a shift with the identity matrix as well as solutions for several different right hand sides. In the past Krylov subspace methods have been developed which try to exploit either the need for solutions to multiple right hand sides (e.g. deflation type methods and block methods) or multiple shifts (e.g. shifted CG) with some success. Though, in some instances (e.g. the Rational Hybrid Monte Carlo algorithm) the computations even require solutions to linear systems for both multiple right hand sides and multiple shifts at the same time. In this talk we present a Krylov subspace method DSBlockCG that, based on a block Lanczos process, exploits both features at once. We give numerical evidence that our method is superior to applying other iterative methods to each of the systems individually as well as in some cases to shifted or block Krylov subspace methods.
Philipp Birken: Preconditioning DG: ROBO-SGS
University of Kassel, GermanyAn important issue in the development of discontinuous Galerkin (DG) methods for flow problems is the design of fast solvers in the case of an implicit time integration, in particular for Navier-Stokes equations. Here, we consider the context of threedimensional unsteady flows. As a solver, time adaptive DIRK methods with preconditioned Jacobian-Free Newton-Krylov (JFNK) methods will be used. We use a polynomial basis that is hierarchical, allowing to obtain approximate Jacobians with significantly sparser blocks corresponding to a reduced order basis. This idea is applied to the off diagonal blocks in SGS, resulting in the ROBO-SGS preconditioner.
Nemanja Bozovic: Recycling Krylov subspace information in sequences of linear systems
Bergische Universität Wuppertal, GermanyMany problems in numerical simulations in physics require the solution of a long sequence of slowly changing linear systems. Based on the work of M. Parks and E. de Sturler we will show how the cost of solving subsequent systems is reduced by recycling selected subspaces generated for previous systems.
Tobias Breiten: Two-sided Krylov subspace methods for nonlinear model reduction
Max-Planck-Institute Magdeburg, GermanyIn this talk, we will discuss a recently introduced approach for reducing a specific class of nonlinear control systems. The basic idea is to first transform the original model into the following quadratic-bilinear control system \begin{align*} \dot{x}(t)&=A_1x(t) + A_2x(t)\otimes x(t) + Nx(t)u(t) + Bu(t) \\ y(t)&=Cx(t), \end{align*} with $A_1,\;N\in\mathbb R^{n\times n},\;A_2 \in \mathbb R^{n\times n^2},\;B,\;C^T\in \mathbb R^n.$ Then, by means of variational analysis, the above system will be characterized via a series of generalized transfer functions. We will show how interpreting $A_2$ as a matricization of a 3-tensor may be used to improve existent model reduction techniques. This will be done by the construction of two-sided Krylov subspace methods that lead to better approximations of the generalized transfer functions and, hence, to a more accurate reduced order model. Moreover, the tensor framework will allow for an efficient computation of the corresponding projection matrices. New and existent approaches will be compared on the basis of some numerical examples.
Caroline Böß: Model order reduction for discrete unstable systems
Allianz Global Corporate & Specialty AG, GermanyMathematical modeling of problems occurring in natural and engineering sciences often results in very large dynamical systems. Efficient techniques for model order reduction are therefore required to reduce the complexity of the system. There exists a variety of methods for systems with different properties. In this talk the focus is on discrete unstable systems on a finite time horizon. Such systems occur in different applications, for example in the field of numerical weather prediction, where large discrete forecast models are used to determine the best estimate of the current state of the atmosphere. Balanced truncation is a well-known and approved model reduction method, but in its original form it is not suitable to reduce the order of unstable models. There already exist approaches for extending this technique to unstable systems, but they do not work properly if the system has many unstable modes. In this talk the model reduction method of alpha-bounded balanced truncation is proposed. It captures the full behavior of the original system successfully, independently of the number of unstable poles. An error bound on the finite time horizon can be derived. In numerical experiments with unstable test models the benefit of using the alpha-bounded approximation method is illustrated.
Andreas Frommer: Error bounds for the sign function
Bergische Universität Wuppertal, GermanyWe consider the computation of $\mbox{sign}(A)b$ for a hermitian matrix $A$ and a vector $b$ using the Lanczos method (or the Lanczos method for a rational approximation of the sign function). Theory developed by Golub and Meurant shows that we can compute a bound of the error at each iterative step, based on several steps of an {\em interior} Lanczos method. In this talk we show that it is algorithmically feasible to obtain the outer Lanczos vectors from the interior ones, so that the error bounds come at very little additional cost. We apply our method to the computation of the overlap operator in lattice QCD and show numerical results.
Seiji Fujino: A proposal of GPBiCGSafe method without reverse recurrence and its estimation
Kyushu University, JapanAfter appearance of IDR(s) iterative method proposed by Sonneveld and van Gijzen, new iterative methods were proposed one after another. For example, IDR(s)Stab(L) method, GBiCGStab(s,L) and IDR(s)-SOR methods were born. We found out that the conventional GPBiCG method based on three term recurrences includes reverse recurrences because of reduction of computational cost. Therefore, we devised a new GPBiCGSafe method without reverse recurrence, and estimated its performance and stability of convergence. Through numerical experiments, we make clear that GPBiCGSafe method outperforms well compared with the conventional iterative methods.
Martin Grepl: Reduced basis a posteriori error bounds for linear-quadratic elliptic optimal control problems
RWTH Aachen, GermanyMany problems in science and engineering can be modeled in terms of optimal control problems goverened by parametrized partial differential equations (PDEs). While the PDE describes the underlying system or component behavior, the parameters often serve to identify a particular configuration of the component --- such as boundary and initial conditions, material properties, and geometry. The solution of PDE-constrained optimal control problems using classical discretization techniques such as finite elements is computationally expensive and time-consuming since the PDE must be solved many times. One way to decrease the computational burden is the surrogate model approach, where the original high-dimensional model is replaced by its reduced order approximation. However, the solution of the reduced order optimal control problem is suboptimal and reliable error estimation is therefore crucial. A posteriori estimates for the error in the optimal control and the associated cost functional have been proposed in [F.Troeltzsch, S.Volkwein, Comp. Opt. Appl., 44(1)(2009), pp. 83-115] and [L.Dede, SIAM J. Sci. Comp., 32:2 (2010), pp. 997-1019], respectively. However, the former bounds, although rigorous, require solution of the high-dimensional problem and are thus online-inefficient; whereas the latter estimates, although efficient, are not rigorous upper bounds for the error. In this talk we present new rigorous and efficiently evaluable a posteriori error bounds for the optimal control and the associated cost functional. Our approach thus allows not only the efficient real-time solution of the reduced optimal control problem, but also the efficient real-time evaluation of the quality of the suboptimal solution. We present numerical results to confirm and test our approach.
Karsten Kahl: Algebraic Multigrid Coarsening by Algebraic Distances and Compatible Relaxation
Bergische Universität Wuppertal, GermanyOne of the most important and difficult tasks in the construction of adaptive algebraic multigrid methods is the determination of suitable coarse variable sets in a purely algebraic way. That is without using additional information about the system of linear equation at hand, e.g., existence and direction of anisotropy. The concept of compatible relaxation which has been developed for this task has shown that it is indeed possible to determine suitable coarse variable sets in an algebraic fashion. Though some promising initial results have been achieved using compatible relaxation coarsening algorithms together with energy minimizing interpolation, a robust and efficient setup algorithm based on these techniques has yet to be realized. In the past, these CR-based schemes have intentionally avoided the use of strength of connection in their construction, making it difficult to find suitable interpolation, which is a main difficulty that requires further investigation. Thus in this talk we introduce the notion of algebraic distance to determine a black-box notion of strength-of-connection that we feed to compatible relaxation in order to on one hand accelerate the coarsening process and on the other hand create the possibility of aggressive coarsening and long range interpolation. We use our approach to construct suitable coarse variable sets for several anisotropic diffusion problems and demonstrate that we are able to construct efficient two and multigrid cycles using least squares interpolation.
Patrick Kürschner: Efficient Handling of Complex Shift Parameters in the Low-rank Cholesky factor ADI method
Max Planck Institute for Dynamics of Complex Technical Systems, GermanyThe solution of large-scale Lyapunov equations is a crucial problem for several fields of modern applied mathematics, e. g., balanced truncation model order reduction. The low-rank Cholesky factor version of the alternating directions implicit method (LRCF-ADI) is an iterative algorithm that computes approximate low-rank factors of the solution. In order to achieve a fast convergence it requires adequate shift parameters, which can be complex in the unsymmetric case. This will require arithmetic computations as well as storage of complex data and thus, increase the overall complexity and memory requirements of the method. In this talk we propose a novel reformulation of LRCF-ADI which generates real low-rank factors by carefully exploiting the dependencies of the iterates with respect to pairs of complex conjugate shift parameters. It significantly reduces the amount of complex arithmetic calculations and memory, and is hence often superior in terms of efficiency compared to other formulations.
Izchak Lewkowicz: Robust Nevanlinna-Pick Interpolation and approximating the Matrix Sign
Dept. of Electrical Engineering, IsraelWhen exists, finding the Sign of a given matrix can always be formulated as a Nevanlinna-Pick Interpolation Problem (NPIP). Practical motivation suggests Approximated NPIP where only bounds on the spectrum of the matrix are given and the corresponding Sign matrix is only approximated (s.t. classical approach converges). This leads to two novel setups of interpolation problems: (i) Robust (ii) Approximated. For simplicity we first illustrate them over polynomials and then in the NPIP framework. If time permits, results from applying this approach to the matrix Sign approximation will be presented.
Alexander Litvinenko: Low-rank direct Bayesian update of polynomial chaos coefficients
Institute for Scientific Computing, GermanyWe present a fully deterministic approach to a probabilistic interpretation of inverse problems in which unknown quantities are represented by random fields or processes, described by a non-Gaussian prior distribution. The description of the introduced random fields is given in a ``white noise'' framework, which enables us to solve the stochastic forward problem through Galerkin projection onto polynomial chaos. With the help of such representation, the probabilistic identification problem is cast in a polynomial chaos expansion setting and the linear Bayesian form of updating.By introducing the Hermite algebra this becomes a direct, purely algebraic way of computing the posterior, which is inexpensive to evaluate. In addition, we show that the well-known Kalman filter method is the low order part of this update. The proposed method has been tested on a stationary diffusion equation with prescribed source terms, characterised by an uncertain conductivity parameter which is then identified from limited and noisy data obtained by a measurement of the diffusing quantity. To speedup the computational process all ingredients of Bayesian update formula are approximated in low-rank data format. The approximation error, memory requirement and computing time are demonstrated on the example from numerical aerodynamic.
Thomas Mach: Computing Inner Eigenvalues of Matrices in Tensor Train Format
Max Planck Institute for Dynamics of Complex Technical Systems, GermanyThe computation of eigenvalues is one of the core topics of numerical mathematics. We will present an eigenvalue algorithm for the computation of inner eigenvalues of large matrices based on the preconditioned inverse iteration \begin{eqnarray*} x_{i+1} = x_{i} - B^{-1}\left(Mx_{i} - \mu(x_{i}) x_{i}\right), \end{eqnarray*} and the folded spectrum method (replace $M$ by $(M-\sigma I)^{2}$). We assume that $M$ is given in the tensor train matrix format \cite{Ose10} and use the TT-toolbox from I.V. Oseledets (see \url{http://spring.inm.ras.ru/osel/}) for the numerical computations. We will present first numerical results and discuss the numerical difficulties. \bibliographystyle{alpha} \begin{thebibliography}{WZ94} \bibitem[Ose10]{Ose10} I.V. Oseledets. \newblock Approximation of $2^d\times 2^d$ matrices using tensor decomposition. \newblock {\em {SIAM} J. Matrix Anal. Appl.}, 31(4):2130--2145, 2010. \end{thebibliography}
Volker Mehrmann: Regularization of descriptor systems
TU Berlin, GermanyWe will discuss the reformulation and regularization of descriptor systems for their use in simulation, control and optimization. Based on local and global staircase froms a behavior ansatz leads to an a reformulation of the system, an idenfication of 'good' inputs and outputs and a 'good' preprocessing and model reduction of the system. This is joint work with Steve Campbell and Peter Kunkel
Heiko Panzer: Iterative factorization of the error system in Moment Matching and applications to error bounds
TU München, GermanyThe factorization of the error system in Krylov subspace methods, that is presented separately beforehands, is shown to be applicable iteratively. Thereby, the error system keeps a certain beneficial structure and can be massaged according to a given objective. Four main features and applications of the novel factorization are presented: its numerical benefit over the classical error system, its potential for physical interpretability, a computationally advantageous Gramian-based H2 error bound and a novel H2 error bound for dissipative or port-Hamiltonian systems.
Matthias Rottmann: Aggregation-based Multilevel Methods for Lattice QCD
University of Wuppertal, GermanyA substantial amount of work in QCD computations is spent solving Lattice Dirac equations. It is well known that most Krylov subspace methods (e.g. CGN, GCR, BiCGStab) suffer from critical slowing down when approaching the critical mass as well as lattice spacing zero. Thus it is of utmost importance to find preconditioners for said methods that remedy these scaling issues. In the recent past preconditioners based on domain decomposition have been proposed that show some promise to speed up calculations, yet it is well-known in the domain decomposition literature that these methods cannot remedy the scaling problems completely without the use of an additional coarse-grid system. In this talk we present a method that combines the domain decomposition approach (SAP) with an algebraic multigrid hierarchy and the concept of K-cycles and show numerical results of its near optimal scalability up to lattices of size $64 x 32^3$.
Jens Saak: A Goal Oriented Low Rank Dual ADI Iteration for Balanced Truncation
Computational Methods in Systems and Control Theory, GermanyThe low rank alternating directions implicit (LR-ADI) iteration has proven to be one of the most efficient methods for solving large scale sparse Lyapunov equations. For Lyapunov based Balanced Truncation model reduction we have to solve two dual Lyapunov equations to compute the system Gramians required for the balancing transformations. Usually the LR-ADI is stopped via residual based criteria. These are expensive in evaluation on the one hand and do not always provide the right stopping information in terms of the final goal on the other hand. For computation of the reduced order model it is not helpful if the residual decay in the LR-ADI is very fast, since the column dimensions of the Gramian factors limit the dimension and thus the accuracy of the reduced order model. Also it has been observed, that in cases where the LR-ADI shows bad convergence behavior, the reduced order model can be very good although the final LR-ADI residual was comparably large. We propose a dual ADI iteration that solves the two dual Lyapunov equations simultaneously. Instead of residual based criteria it uses a goal oriented stopping criterion based on the Hankel singular value approximations.
André Schneider: Balanced Truncation for Descriptor Systems with Many Terminals
Max Planck Gesellschaft, GermanyThe model reduction method introduced in [Benner, P. and Schneider, A.; Balanced Truncation Model Order Reduction for LTI Systems with many Inputs or Outputs, in A. Edelmayer: Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems, 2010, ISBN/ISSN: 978-963-311-370-7] shows how to reduce linear time invariant (LTI) continuous time state space systems with either many inputs or many outputs using the well-known balanced truncation approach. We call this method balanced truncation for many terminals (BTMT). In this talk we generalize BTMT to descriptor systems, where $m\in {\mathcal O}(n)$ and $p \ll n$, or vice versa. We explain how to obtain the reduced order model by solving one Lyapunov equation and using the Gau{\ss}-Kronrod quadrature to compute the needed projection matrices. We also discuss the case that $E$ is singular and show numerical results. This is joint work with Prof. P. Benner.
Nguyen Thanh Son: Model reduction for parameter dependent systems with Grassmann manifold interpolation
University of Bremen, GermanyModel Order Reduction (MOR) helps to reduce the computations in dealing with the mathematical models of large dynamical systems. In many cases, the considered models depend on parameters; MOR techniques are, therefore, preferred to symbolically preserve this dependence or to be adaptive to the change of systems caused by the variation in the values of parameters. In this paper, we demonstrate that the interpolation technique on Grassmann manifolds can be applied to fulfill this requirement. We, moreover, improve the proposed method by considerably reducing the computational complexity of the method through decomposing the whole procedure into \textit{offline} and \textit{online} stages. A numerical example illustrates the method as well as to proves its effectiveness.
Paul van Dooren: Updating indefinite matrix approximations
Catholic University of Louvain, BelgiumIndefinite symmetric matrices occur in many applications, such as optimization, partial differential equations and variational problems where they are for instance linked to a so-called saddle point problem. In these applications one is often interested in computing an estimate of the dominant eigenspace of such matrices. In this paper we propose an incremental method to compute an estimate of the dominant eigenbasis of such matrices. This method is well-suited for large scale problems since it is efficient in terms of complexity as well as data management.
Heinrich Voss: Large-Scale Tikhonov Regularization of Total Least Squares Problems
Hamburg University of Technology, GermanyThe total least squares (TLS) method is a successful approach for linear problems when not only the right-hand side but the system matrix as well are contaminated by some noise. For ill-posed TLS problems regularization is necessary to stabilize the computed solution. In this presentation we present a new approach for computing an approximate solution of the Tikhonov-regularized large-scale total least-squares problem. An iterative method is proposed which solves a convergent sequence of projected linear systems and thereby builds up a highly suitable search space. This is joint work with Joerg Lampe
Georg Vossen: Error analysis for ${\cal H}_{2,\alpha}$-norm optimal model reduction in optimal control problems
RWTH Aachen University, GermanyWe present a numerical solution method for optimal control problems which are subject to parabolic and hyperbolic evolution equations. The partial differential equation is semi-discretized in space to obtain a large-scale linear time invariant dynamical system with the boundary or distributed controls as input and those parts of the discretized state appearing in the cost functional as output variables. The corresponding transfer function is approximated optimally with respect to the ${\cal H}_{2,\alpha}$-norm leading to a reduced dynamical system which induces an optimally reduced optimal control problem. A-posteriori error analysis is applied to quantify the approximation quality of the solution of the optimally reduced optimal control problem. Algorithms on basis of the error analysis will be presented which ensure a prescribed error in the optimal control. The methods are illustrated by numerical examples and compared to other reduction methods.
Thomas Wolf: Krylov subspaces and Sylvester equations
Technische Universität München, GermanyIn this talk the connection between Krylov subspaces and the solutions of Sylvester equations is presented. Previous results on Krylov subspaces solving Sylvester equations are revised and equipped with new proofs. Furthermore, a new Sylvester equation for the same Krylov subspace is introduced. It will be shown that there are infinitely many Sylvester equations of that kind. Accordingly, every Krylov subspace represents infinitely many Krylov subspaces where the respective starting vectors and expansion points can be given. Additionally, the results are used to ease investigation of the error in Krylov based model order reduction.
Ralf Zimmermann: On Efficiently Updating Singular Value Decomposition Based Reduced Order Models
DLR, German Aerospace Center, GermanyEfficiently updating an SVD-based data representation while keeping accurate track of the data mean when new observations are coming in is a common objective in many practical application scenarios. In this talk, two different SVD update algorithms capable of treating an arbitrary number of new observations are introduced following the symmetric EVD philosophy. These methods are compared to an SVD update method known from the literature. The comparison criterion of interest is the theoretical computational complexity, it being understood that the dimension of the observation vectors is much larger than the number of observations. From this point of view, a hierarchy of methods is derived, and the computational savings of the update strategies persuing the symmetric EVD approach are demonstrated. It is exposed, how the compression level of the initial SVD model affects the performance of these algorithms and the break point where one method becomes more efficent than the other is determined. In addition, simple rules of thumb are derived for easing the choice of an algorithm valid in most practical scenarios.
