Existence of a low rank or ℋ-matrix approximant to the solution of a Sylvester equation.

We consider the Sylvester equation AX-XB+C=0 where the matrix C∈ℂn×m is of low rank and the spectra of A∈ℂn×n and B∈ℂm×m are separated by a line. We prove that the singular values of the solution X decay exponentially, that means for any ℇ∈(0,1) there exists a matrix &Xtilde; of rank k=O(log(1/ℇ)) such that ∥X-&Xtilde;∥2⩽ℇ∥X∥2. As a generalization we prove that if A,B,C are hierarchical matrices then the solution X can be approximated by the hierarchical matrix format described in Hackbusch (Computing 2000; 62: 89–108). The blockwise rank of the approximation is again proportional to log(1/ℇ). Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]