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 X̃ of rank k = O (log(1/ ε )) such that ∥ X − X̃ ∥ 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.