Computing real low-rank solutions of Sylvester equations by the factored ADI method

We investigate the factored alternating directions implicit (ADI) iteration for large and sparse Sylvester equations. A novel low-rank expression for the associated Sylvester residual is established which enables cheap computations of the residual norm along the iteration, and which yields a reformulated factored ADI iteration. The application to generalized Sylvester equations is considered as well. We also discuss the efficient handling of complex shift parameters and reveal interconnections between the ADI iterates w.r.t. those complex shifts. This yields a further modification of the factored ADI iteration which employs only an absolutely necessary amount of complex arithmetic operations and storage, and which produces low-rank solution factors consisting of entirely real data. Certain linear matrix equations, such as, e.g., cross Gramian Sylvester and Stein equations, are in fact special cases of generalized Sylvester equations and we show how specially tailored low-rank ADI iterations can be deduced from the generalized factored ADI iteration. (C) 2014 Elsevier Ltd. All rights reserved.