We consider the problem of efficiently solving Sylvester and Lyapunov equations of medium and large scale, in case of rank-structured data, i.e., when the coefficient matrices and the right-hand side have low-rank off-diagonal blocks. This comprises problems with banded data, recently studied in [A. Haber and M. Verhaegen, Automatica J. IFAC, 73 (2016), pp. 256--268; D. Palitta and V. Simoncini, Numerical Methods for Large-Scale Lyapunov Equations with Symmetric Banded Data, preprint, arxiv, 1711.04187, 2017], which often arise in the discretization of elliptic PDEs. We show that, under suitable assumptions, the quasiseparable structure is guaranteed to be numerically present in the solution, and explicit novel estimates of the numerical rank of the offdiagonal blocks are provided. Efficient solution schemes that rely on the technology of hierarchical matrices are described, and several numerical experiments confirm the applicability and efficiency of the approaches. We develop a MATLAB toolbox that allows easy replication of the experiments and a ready-to-use interface for the solvers. The performances of the different approaches are compared, and we show that the new methods described are efficient on several classes of relevant problems.

Massei, S., Palitta, D., Robol, L. (2018). Solving Rank-Structured Sylvester and Lyapunov Equations. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 39(4), 1564-1590 [10.1137/17M1157155].

Solving Rank-Structured Sylvester and Lyapunov Equations

Palitta, Davide
Membro del Collaboration Group
;
2018

Abstract

We consider the problem of efficiently solving Sylvester and Lyapunov equations of medium and large scale, in case of rank-structured data, i.e., when the coefficient matrices and the right-hand side have low-rank off-diagonal blocks. This comprises problems with banded data, recently studied in [A. Haber and M. Verhaegen, Automatica J. IFAC, 73 (2016), pp. 256--268; D. Palitta and V. Simoncini, Numerical Methods for Large-Scale Lyapunov Equations with Symmetric Banded Data, preprint, arxiv, 1711.04187, 2017], which often arise in the discretization of elliptic PDEs. We show that, under suitable assumptions, the quasiseparable structure is guaranteed to be numerically present in the solution, and explicit novel estimates of the numerical rank of the offdiagonal blocks are provided. Efficient solution schemes that rely on the technology of hierarchical matrices are described, and several numerical experiments confirm the applicability and efficiency of the approaches. We develop a MATLAB toolbox that allows easy replication of the experiments and a ready-to-use interface for the solvers. The performances of the different approaches are compared, and we show that the new methods described are efficient on several classes of relevant problems.
2018
Massei, S., Palitta, D., Robol, L. (2018). Solving Rank-Structured Sylvester and Lyapunov Equations. SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 39(4), 1564-1590 [10.1137/17M1157155].
Massei, Stefano; Palitta, Davide; Robol, Leonardo
File in questo prodotto:
File Dimensione Formato  
17m1157155.pdf

accesso aperto

Descrizione: Articolo
Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 702.99 kB
Formato Adobe PDF
702.99 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/648854
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 28
  • ???jsp.display-item.citation.isi??? 24
social impact