A multigrid method to solve large scale Sylvester equations. (English) Zbl 1154.65024

Grasedyck, Lars; Hackbusch, Wolfgang

SIAM J. Matrix Anal. Appl. 29, No. 3, 870-894 (2007).

The authors consider the Sylvester matrix equation \(AX-XB+ C=0\), where \(A\) and \(-B\) are stiffness matrices from the discretization of a linear elliptic partial differential operator, the matrix \(C\) is of low rank given in factorized form. They develop a multigrid method for computing a low rank approximation to the solution. They use the usual Jacobian smoother and standard prolongation and restriction operators but extend the basic multigrid cycle by a projection step that ensures that the rank of each iterate is bounded. The algorithm is of linear complexity instead of quadratic complexity.

Reviewer: Liu Xinguo (Qingdao)

MSC:

65F30	Other matrix algorithms (MSC2010)
65F05	Direct numerical methods for linear systems and matrix inversion
65F50	Computational methods for sparse matrices
15A24	Matrix equations and identities

Keywords:

multigrid method; low rank approximation; fast solver; Lyapunov equation; Riccati equation; Sylvester matrix equation; algorithm; linear complexity