Solving large scale quasiseparable Lyapunov equations

We consider the problem of efficiently solving Lyapunov and Sylvester equations of medium and large scale, in the case where all the coefficients are quasiseparable, i.e., they have off-diagonal blocks of low-rank. This comprises the case with banded coefficients and right-hand side, recently studied in [6, 9]. We show that, under suitable assumptions, this structure is guaranteed to be numer- ically present in the solution, and we provide explicit estimates of the numerical rank of the off-diagonal blocks. Moreover, we describe an efficient method for approximating the solution, which relies on the technology of hierarchical matrices. A theoretical characterization of the quasiseparable structure in the solution is pre- sented, and numerically experiments confirm the applicability and efficiency of our ap- proach. We provide a MATLAB toolbox that allows easy replication of the experiments and a ready-to-use interface for our solver.