A MULTIGRID METHOD TO SOLVE LARGE SCALE SYLVESTER EQUATIONS.

We consider the Sylvester equation AX -XB+C = 0, where the matrix C ϶ Rn×m is of low rank and the spectra of A ϶ Rn×n and B ϶ Rm×m 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 discretizations. Here the matrices A and B each stem from the discretization of a partial differential operator of elliptic type. The algorithm is of complexity O(n+m), or, more precisely, if the solution can be represented with (n + m)k data (k ∼ log(n + m)), then the complexity of the algorithm is O((n + m)k2). [ABSTRACT FROM AUTHOR]