Search

We consider the low-rank alternating directions implicit (ADI) iteration for approximately solving large-scale algebraic Sylvester equations. Inside every iteration step of this iterative process a pair of linear systems of equations has to be solved. We investigate the situation when those inner linear systems are solved inexactly by an iterative methods such as, for example, preconditioned Krylov subspace methods. The main contribution of this work are thresholds for the required accuracies regarding the inner linear systems which dictate when the employed inner Krylov subspace methods can be safely terminated. The goal is to save computational effort by solving the inner linear system as inaccurate as possible without endangering the functionality of the low-rank Sylvester-ADI method. Ideally, the inexact ADI method mimics the convergence behaviour of the more expensive exact ADI method, where the linear systems are solved directly. Alongside the theoretical results, also strategies for an actual practical implementation of the stopping criteria are developed. Numerical experiments confirm the effectiveness of the proposed strategies.

Low-rank Krylov methods are one of the few options available in the literature to address the numerical solution of large-scale general linear matrix equations. These routines amount to well-known Krylov schemes that have been equipped with a couple of low-rank truncations to maintain a feasible storage demand in the overall solution procedure. However, such truncations may affect the convergence properties of the adopted Krylov method. In this paper we show how the truncation steps have to be performed in order to maintain the convergence of the Krylov routine. Several numerical experiments validate our theoretical findings.

In this work, we consider two types of large-scale quadratic matrix equations: Continuous-time algebraic Riccati equations, which play a central role in optimal and robust control, and unilateral quadratic matrix equations, which arise from stochastic processes on 2D lattices and vibrating systems. We propose a simple and fast way to update the solution to such matrix equations under low-rank modifications of the coefficients. Based on this procedure, we develop a divide-and-conquer method for quadratic matrix equations with coefficients that feature a specific type of hierarchical low-rank structure, which includes banded matrices. This generalizes earlier work on linear matrix equations. Numerical experiments indicate the advantages of our newly proposed method versus iterative schemes combined with hierarchical low-rank arithmetic.

In this paper, balancing based model order reduction (MOR) for large-scale linear discrete-time time-invariant systems in prescribed finite time intervals is studied. The first main topic is the development of error bounds regarding the approximated output vector within the time limits. The influence of different components in the established bounds will be highlighted. After that, the second part of the article proposes strategies that enable an efficient numerical execution of time-limited balanced truncation for large-scale systems. Numerical experiments illustrate the performance of the proposed techniques., Comment: 23 pages, 4 figures

The low-rank alternating directions implicit (LR-ADI) iteration is a frequently employed method for efficiently computing low-rank approximate solutions of large-scale Lyapunov equations. In order to achieve a rapid error reduction, the iteration requires shift parameters whose selection and generation is often a difficult task, especially for nonsymmetric coefficients in the Lyapunov equation. This article represents a follow up of Benner et al. [ETNA, 43 (2014-2015), pp. 142-162] and investigates self-generating shift parameters based on a minimization principle for the Lyapunov residual norm. Since the involved objective functions are too expensive to evaluate and, hence, intractable, compressed objective functions are introduced which are efficiently constructed from the available data generated by the LR-ADI iteration. Several numerical experiments indicate that these residual minimizing shifts using approximated objective functions outperform existing precomputed and dynamic shift parameter selection techniques, although their generation is more involved.

In this paper, we discuss numerical methods for solving large-scale continuous-time algebraic Riccati equations. These methods have been the focus of intensive research in recent years, and significant progress has been made in both the theoretical understanding and efficient implementation of various competing algorithms. There are several goals of this manuscript: first, to gather in one place an overview of different approaches for solving large-scale Riccati equations, and to point to the recent advances in each of them. Second, to analyze and compare the main computational ingredients of these algorithms, to detect their strong points and their potential bottlenecks. And finally, to compare the effective implementations of all methods on a set of relevant benchmark examples, giving an indication of their relative performance.

The rational Krylov subspace method (RKSM) and the low-rank alternating directions implicit (LR-ADI) iteration are established numerical tools for computing low-rank solution factors of large-scale Lyapunov equations. In order to generate the basis vectors for the RKSM, or extend the low-rank factors within the LR-ADI method the repeated solution to a shifted linear system is necessary. For very large systems this solve is usually implemented using iterative methods, leading to inexact solves within this inner iteration. We derive theory for a relaxation strategy within these inexact solves, both for the RKSM and the LR-ADI method. Practical choices for relaxing the solution tolerance within the inner linear system are then provided. The theory is supported by several numerical examples., Comment: 31 pages, 4 figures, 2 tables

Recovering brain connectivity from tract tracing data is an important computational problem in the neurosciences. Mesoscopic connectome reconstruction was previously formulated as a structured matrix regression problem (Harris et al., 2016), but existing techniques do not scale to the whole-brain setting. The corresponding matrix equation is challenging to solve due to large scale, ill-conditioning, and a general form that lacks a convergent splitting. We propose a greedy low-rank algorithm for connectome reconstruction problem in very high dimensions. The algorithm approximates the solution by a sequence of rank-one updates which exploit the sparse and positive definite problem structure. This algorithm was described previously (Kressner and Sirkovi\'c, 2015) but never implemented for this connectome problem, leading to a number of challenges. We have had to design judicious stopping criteria and employ efficient solvers for the three main sub-problems of the algorithm, including an efficient GPU implementation that alleviates the main bottleneck for large datasets. The performance of the method is evaluated on three examples: an artificial "toy" dataset and two whole-cortex instances using data from the Allen Mouse Brain Connectivity Atlas. We find that the method is significantly faster than previous methods and that moderate ranks offer good approximation. This speedup allows for the estimation of increasingly large-scale connectomes across taxa as these data become available from tracing experiments. The data and code are available online.

When solving partial differential equations numerically, usually a high order spatial discretization is needed. Model order reduction (MOR) techniques are often used to reduce the order of spatially-discretized systems and hence reduce computational complexity. A particular MOR technique to obtain a reduced order model (ROM) is balanced truncation (BT). However, if one aims at finding a good ROM on a certain finite time interval only, time-limited BT (TLBT) can be a more accurate alternative. So far, no error bound on TLBT has been proved. In this paper, we close this gap in the theory by providing an $\mathcal H_2$ error bound for TLBT with two different representations. The performance of the error bound is then shown in several numerical experiments.

In this article we investigate model order reduction of large-scale systems using time-limited balanced truncation, which restricts the well known balanced truncation framework to prescribed finite time intervals. The main emphasis is on the efficient numerical realization of this model reduction approach in case of large system dimensions. We discuss numerical methods to deal with the resulting matrix exponential functions and Lyapunov equations which are solved for low-rank approximations. Our main tool for this purpose are rational Krylov subspace methods. We also discuss the eigenvalue decay and numerical rank of the solutions of the Lyapunov equations. These results, and also numerical experiments, will show that depending on the final time horizon, the numerical rank of the Lyapunov solutions in time-limited balanced truncation can be smaller compared to standard balanced truncation. In numerical experiments we test the approaches for computing low-rank factors of the involved Lyapunov solutions and illustrate that time-limited balanced truncation can generate reduced order models having a higher accuracy in the considered time region.

In this work, we study the numerical approximation of local fluctuations of certain classes of parabolic stochastic partial differential equations (SPDEs). Our focus is on effects for small spatially-correlated noise on a time scale before large deviation effects have occurred. In particular, we are interested in the local directions of the noise described by a covariance operator. We introduce a new strategy and prove a Combined ERror EStimate (CERES) for the five main errors: the spatial discretization error, the local linearization error, the noise truncation error, the local relaxation error to steady state, and the approximation error via an iterative low-rank matrix algorithm. In summary, we obtain one CERES describing, apart from modelling of the original equations and standard round-off, all sources of error for a local fluctuation analysis of an SPDE in one estimate. To prove our results, we rely on a combination of methods from optimal Galerkin approximation of SPDEs, covariance moment estimates, analytical techniques for Lyapunov equations, iterative numerical schemes for low-rank solution of Lyapunov equations, and working with related spectral norms for different classes of operators., Comment: 25 pages; preprint

The convergence of GMRES for solving linear systems can be influenced heavily by the structure of the right hand side. Within the solution of eigenvalue problems via inverse iteration or subspace iteration, the right hand side is generally related to an approximate invariant subspace of the linear system. We give detailed and new bounds on (block) GMRES that take the special behavior of the right hand side into account and explain the initial sharp decrease of the GMRES residual. The bounds give rise to adapted preconditioners applied to the eigenvalue problems, e.g. tuned and polynomial preconditioners. The numerical results show that the new (block) GMRES bounds are much sharper than conventional bounds and that preconditioned subspace iteration with either a tuned or polynomial preconditioner should be used in practice., Comment: second revised version

This paper introduces a new algorithm for solving large-scale continuous-time algebraic Riccati equations (CARE). The advantage of the new algorithm is in its immediate and efficient low-rank formulation, which is a generalization of the Cholesky-factored variant of the Lyapunov ADI method. We discuss important implementation aspects of the algorithm, such as reducing the use of complex arithmetic and shift selection strategies. We show that there is a very tight relation between the new algorithm and three other algorithms for CARE previously known in the literature -- all of these seemingly different methods in fact produce exactly the same iterates when used with the same parameters: they are algorithmically different descriptions of the same approximation sequence to the Riccati solution.