Conference abstracts

Session B7 - Numerical Linear Algebra

July 14, 17:00 ~ 17:30

Numerical methods for Lyapunov matrix equations with banded symmetric data

Valeria Simoncini

Dipartimento di Matematica, Universita' di Bologna, Italy   -   valeria.simoncini@unibo.it

We are interested in the numerical solution of the large-scale Lyapunov equation \[ A{\mathbf X}+{\mathbf X}A^T=C, \] where $A,C\in\cal{R}^{n\times n}$ are both large and banded matrices. We suppose that $A$ is symmetric and positive definite and $C$ is symmetric and positive semidefinite. While the case of low rank $C$ has been successfully addressed in the literature, the more general banded setting has not received much attention, in spite of its possible occurrence in applications. In this talk we aim to fill this gap.

It has been recently shown that if $A$ is well conditioned, the entries of the solution matrix $\mathbf X$ decay in absolute value as their indexes move away from the sparsity pattern of $C$. This property can be used in a memory-saving matrix-oriented Conjugate Gradient method to obtain a banded approximate solution.

For $A$ not well conditioned, the entries of $\mathbf X$ do not sufficiently decay to derive a good banded approximation. Nonetheless, we show that it is possible to split $\mathbf X$ as $\mathbf X=\mathbf Z_b + \mathbf Z_r$, where $\mathbf Z_b$ is banded and $\mathbf Z_r$ is numerically low rank. We thus propose a novel strategy that efficiently approximates both $\mathbf Z_b$ and $\mathbf Z_r$ with acceptable memory requirements.

Numerical experiments are reported to illustrate the potential of the discussed methods.

Joint work with Davide Palitta (Universita' di Bologna, Italy).

View abstract PDF



FoCM 2017, based on a nodethirtythree design.