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 formula12 matrix is of low rank and the spectra of the formula14 and formula16 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 formula28, or, more precisely, if the solution can be represented with formula30 data then the complexity of the algorithm is formula32.

03.07.2017, 01:41