Search

MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint
48/2004

A Multigrid Method to Solve Large Scale Sylvester Equations

Lars Grasedyck and Wolfgang Hackbusch

Abstract

We consider the Sylvester equation $AX-XB+C=0$, where the $n\times m$ matrix is of low rank and the spectra of the $n\times n$ and $m\times m$ matrices $A$,$B$ are separated by a line. The solution $X$ can be approximated in a data-sparse format and we develop a multigrid algorithm that computes the solution in this format. For the multigrid method to work we need a hierarchy of discretisations, i.e., the matrices $A$ and $B$ each stem from the discretisation of some partial differential operator of elliptic type. The algorithm is of complexity $\mathcal{O}(n+m)$, or, more precisely, if the solution can be represented with $(n+m)\log(n+m)$ data then the complexity of the algorithm is $\mathcal{O}((n+m)\log(n+m)^{2})$.

Received:
Jul 22, 2004
Published:
Jul 22, 2004
MSC Codes:
65F05, 65F30, 65F50
Keywords:
sylvester equation, low rank approximation, multigrid method

Related publications

inJournal
2007 Repository Open Access
Lars Grasedyck and Wolfgang Hackbusch

A multigrid method to solve large scale Sylvester equations

In: SIAM journal on matrix analysis and applications, 29 (2007) 3, pp. 870-894