Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

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:
22.07.04
Published:
22.07.04
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