Reorthogonalization for the Golub-Kahan-Lanczos bidiagonal reduction (Q1955641): Difference between revisions

The Lanczos method of \textit{G. Golub} and \textit{W. Kahan} [J. Soc. Ind. Appl. Math., Ser. B, Numer. Anal. 2, 205--224 (1965; Zbl 0194.18201)] computes \(A=UBV^T\) where \(A,U\in \mathbb{R}^{m\times n}\), \(B,V\in\mathbb{R}^{n\times n}\), \(B\) upper-bidiagonal, and \(U^TU=I_n=V^TV\) as a first step in computing the singular values of \(A\). Finite arithmetic computations need re-orthogonalization. \textit{H. D. Simon} and \textit{H. Zha} [SIAM J. Sci. Comput. 21, No. 6, 2257--2274 (2000; Zbl 0962.65038)] proposed to do that for only one of both \(U\) and \(V\). Here this is obtained by a one-sided Householder \(QR\) factorization of \(\left[\begin{matrix} 0_{n\times k}\cr AV_k\end{matrix}\right]\). An error analysis shows that the method generates exact Krylov spaces for a nearby matrix. The relative perturbation (in Frobenius norm) is of the order of the sum of the machine precision and the norm of the off-diagonal part of \(V^TV\) (loss of orthogonality). It is shown that the order of convergence is maintained. The components of the algorithm are described in detail.