A unification of unitary similarity transforms to compressed representations (Q652255): Difference between revisions

The authors propose algorithms which rely on the \(QR\)-factorization of the involved matrices. Even though using the \(QR\)-factorization for Hessenberg (H) matrices seems redundant, for many classes of structured rank matrices it provides means for a compact representation. Structured rank matrices are generally dense, and storing the low rank relations can be done effectively for many matrices by storing the \(QR\)-factorization. An important example is the companion matrix, which is a structured rank H matrix. Storing it by a specific \(QR\)-decomposition enables the development of fast \(QR\)-algorithms, gaining one order in computation time for the global eigenvalue computations. A new similarity transformation to H-like form is presented. Comparing this new approach with the classical methods, one notes that this method is much faster (comparable in time to the reduction to H form) and moreover it provides the missing link with rational Krylov. The use of the \(QR\)-factorization for deducing the similarity transformation has several extra advantages. First, when considering both the reduction to H and H-like form from the \(QR\)-viewpoint, many similarities become apparent providing a unified framework for both matrix types. Second, starting from the reduction to H form, the reduction to generalized H form (having more subdiagonals) is trivial; adapting the classical reduction to H-like form for retrieving a generalized H-like is far from trivial and computationally expensive. The unifying framework, however, enables one to derive such reductions in a straightforward manner. Finally, utilizing the \(QR\)-factorization enables one to derive new reduction algorithms. Though this is more of a theoretical interest it plainly illustrates the new insights obtained by working with the \(QR\)-factorization. It is shown that the reduction to H-like form inherits the convergence to the rational Ritz-values rather than the standard convergence. This is illustrated by a numerical experiment where the (rational) Ritz-values are plotted with respect to the order of the submatrix already in H(-like) form, revealing that for the reduction to H-like form the eigenvalues of this submatrix show a rational Ritz-value convergence behavior.