A structured rank-revealing method for Sylvester matrix (Q2469622)

A fast rank-revealing algorithm for computing the numerical rank of a Sylvester matrix is obtained by exploiting the displacement structure of Sylvester matrices. The algorithm is based on the fast Cholesky factorization of \(S^TS\) or \(H^TH\) and relies on the generalized Schur algorithm for matrices with displacement structure. It costs \(O(r(n+m))\) flops, where \(n+m\) and \(r\) are the size and the numerical rank of \(S\). Here \(H\) is the Hankel variation of the Sylvester matrix \(S\). Numerical tests show that the algorithm is valid for Sylvester matrices with low rank deficiency.