TY - JOUR

T1 - Reorthogonalization for the Golub-Kahan-Lanczos bidiagonal reduction

AU - Barlow, Jesse L.

N1 - Funding Information:
The research of Jesse L. Barlow was supported by the National Science Foundation under Grant No. CCF-0429481 and CCF-1115704.

PY - 2013/5

Y1 - 2013/5

N2 - The Golub-Kahan-Lanczos (GKL) bidiagonal reduction generates, by recurrence, the matrix factorization of X ∈ ℝm×n, m≥n, given by X = UBVT where U ∈ ℝm×n is left orthogonal, V ∈ ℝm×n is orthogonal, and B ∈ ℝm×n is bidiagonal. When the GKL recurrence is implemented in finite precision arithmetic, the columns of U and V tend to lose orthogonality, making a reorthogonalization strategy necessary to preserve convergence of the singular values. The use of an approach started by Simon and Zha (SIAM J Sci Stat Comput, 21:2257-2274, 2000) that reorthogonalizes only one of the two left orthogonal matrices U and V is shown to be very effective by the results presented here. Supposing that V is the matrix reorthogonalized, the reorthogonalized GKL algorithm proposed here is modeled as the Householder Q-R factorization of, where Vk = V(:,1:k). That model is used to show that if εM is the machine unit and, where tril(·) is the strictly lower triangular part of the contents, then: (1) the GKL recurrence produces Krylov spaces generated by a nearby matrix X + δX, {double pipe}δ X{double pipe}F = O (εM + n̄) {double pipe}X{double pipe}F; (2) singular values converge in the Lanczos process at the rate expected from the GKL algorithm in exact arithmetic on a nearby matrix; (3) a new proposed algorithm for recovering leading left singular vectors produces better bounds on loss of orthogonality and residual errors.

AB - The Golub-Kahan-Lanczos (GKL) bidiagonal reduction generates, by recurrence, the matrix factorization of X ∈ ℝm×n, m≥n, given by X = UBVT where U ∈ ℝm×n is left orthogonal, V ∈ ℝm×n is orthogonal, and B ∈ ℝm×n is bidiagonal. When the GKL recurrence is implemented in finite precision arithmetic, the columns of U and V tend to lose orthogonality, making a reorthogonalization strategy necessary to preserve convergence of the singular values. The use of an approach started by Simon and Zha (SIAM J Sci Stat Comput, 21:2257-2274, 2000) that reorthogonalizes only one of the two left orthogonal matrices U and V is shown to be very effective by the results presented here. Supposing that V is the matrix reorthogonalized, the reorthogonalized GKL algorithm proposed here is modeled as the Householder Q-R factorization of, where Vk = V(:,1:k). That model is used to show that if εM is the machine unit and, where tril(·) is the strictly lower triangular part of the contents, then: (1) the GKL recurrence produces Krylov spaces generated by a nearby matrix X + δX, {double pipe}δ X{double pipe}F = O (εM + n̄) {double pipe}X{double pipe}F; (2) singular values converge in the Lanczos process at the rate expected from the GKL algorithm in exact arithmetic on a nearby matrix; (3) a new proposed algorithm for recovering leading left singular vectors produces better bounds on loss of orthogonality and residual errors.

UR - http://www.scopus.com/inward/record.url?scp=84877769119&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84877769119&partnerID=8YFLogxK

U2 - 10.1007/s00211-013-0518-8

DO - 10.1007/s00211-013-0518-8

M3 - Article

AN - SCOPUS:84877769119

SN - 0029-599X

VL - 124

SP - 237

EP - 278

JO - Numerische Mathematik

JF - Numerische Mathematik

IS - 2

ER -