LAPACK-STYLE ALGORITHMS AND SOFTWARE FOR SOLVING THE GENERALIZED SYLVESTER EQUATION AND ESTIMATING THE SEPARATION BETWEEN REGULAR MATRIX PAIRS

Robust and fast software to solve the generalized Sylvester equation ( AR - LB = C, DR - LE = F) for unknowns R and L is presented. This spec ial linear system of equations, and its transpose, arises in computing error bounds for computed eigenvalues and eigenspaces of the generali zed eigenvalue problem S - lambda T, in computing deflating subspaces of the same problem, and in computing certain decompositions of transf er matrices arising in control theory. Our contributions are twofold. First, we reorganize the standard algorithm for this problem to use Le vel 3 BLAS operations, like matrix multiplication, in its inner loop. This speeds up the algorithm by a factor of 9 on an IBM RS6000. Second , we develop and compare several condition estimation algorithms, whic h inexpensively but accurately estimate the sensitivity of the solutio n of this linear system.