The Refined Joint Bidiagonalization Method and an Implicitly Restarted Algorithm for Large GSVD Computations

Abstract

We make a convergence analysis on the joint bidiagonalization (JBD) method that computes several extreme generalized singular value decomposition (GSVD) components of a regular matrix pair $\{A,L\}$, and show that the right and left Ritz vectors obtained by it may converge erratically and even may fail to converge, while Ritz values converge. These convergence results hold for a class of general Rayleigh--Ritz projection methods for the GSVD problem under the hypothesis that the deviation of a desired right generalized singular vector from the right subspace tends to zero. We prove the interlacing property of Ritz values and generalized singular values, and extend it to the generalized singular values of $\{A,L\}$ and the matrix pairs consisting of subsets of its columns. To overcome the irregular convergence or possible non-convergence of the JBD method, we nontrivially extend the refined Rayleigh--Ritz projection for the eigenvalue problem to the GSVD problem, and propose a refined JBD (RJBD) method that replaces the right Ritz vectors by new approximations, called the right refined Ritz vectors, satisfying certain residual optimality; we define new approximate left generalized singular vectors, called the left refined Ritz vectors. We prove that the left and right refined Ritz vectors unconditionally converge under the same hypothesis. We extend the implicit restarting scheme to the RJBD method, and develop an implicitly restarted RJBD algorithm with the refined shifts proposed. Numerical experiments illustrate that the new algorithm is at least competitive and often considerably more efficient than the implicitly restarted JBD algorithm.