

Preprint 48/2004
A Multigrid Method to Solve Large Scale Sylvester Equations
Lars Grasedyck and Wolfgang Hackbusch
Contact the author: Please use for correspondence this email.
Submission date: 22. Jul. 2004 (revised version: May 2007)
Pages: 27
published in: SIAM journal on matrix analysis and applications, 29 (2007) 3, p. 870-894
DOI number (of the published article): 10.1137/040618102
Bibtex
MSC-Numbers: 65F05, 65F30, 65F50
Keywords and phrases: sylvester equation, low rank approximation, multigrid method
Download full preprint: PDF (366 kB), PS ziped (314 kB)
Abstract:
We consider the Sylvester equation AX-XB+C=0, where the matrix
is of low rank and the spectra of the
and
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
, or, more precisely, if the
solution can be represented with
data then the complexity
of the algorithm is
.