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 .