Articolo in rivista, 2019, ENG, 10.1137/17M1161038

Low-rank updates and a divide-and-conquer method for linear matrix equations

Kressner D.; Massei S.; Robol L.

EPFL, Lausanne, Switzerland; EPFL, Lausanne, Switzerland; University of Pisa, Pisa, Italy; CNR-ISTI, Pisa, Italy

Linear matrix equations, such as the Sylvester and Lyapunov equations, play an important role in various applications, including the stability analysis and dimensionality reduction of linear dynamical control systems and the solution of partial differential equations. In this work, we present and analyze a new algorithm, based on tensorized Krylov subspaces, for quickly updating the solution of such a matrix equation when its coefficients undergo low-rank changes. We demonstrate how our algorithm can be utilized to accelerate the Newton method for solving continuous-time algebraic Riccati equations. Our algorithm also forms the basis of a new divide-and-conquer approach for linear matrix equations with coefficients that feature hierarchical low-rank structure, such as hierarchically off-diagonal low-rank structures, hierarchically semiseparable, and banded matrices. Numerical experiments demonstrate the advantages of divide-and-conquer over existing approaches, in terms of computational time and memory consumption.

SIAM journal on scientific computing (Print) 41 (2)

Keywords

Divide-and-conquer, Hierarchical matrices, Low-rank update, Lyapunov equation, Sylvester equation

CNR authors

Robol Leonardo

CNR institutes

ISTI – Istituto di scienza e tecnologie dell'informazione "Alessandro Faedo"

ID: 402965

Year: 2019

Type: Articolo in rivista

Creation: 2019-05-21 13:52:36.000

Last update: 2020-10-12 17:16:00.000

CNR authors

External IDs

CNR OAI-PMH: oai:it.cnr:prodotti:402965

DOI: 10.1137/17M1161038

Scopus: 2-s2.0-85065470933

ISI Web of Science (WOS): 000469225300007