GolubKahanBidiagonalisierung

Golub–Kahan bidiagonalization is an algorithm in numerical linear algebra for reducing a general m-by-n matrix to bidiagonal form using two orthogonal transformations. For a real or complex matrix A, the method constructs orthogonal matrices U and V such that A = U B V^T, where B is bidiagonal (nonzero on the main diagonal and either the superdiagonal or subdiagonal). The process is named after Gene H. Golub and William Kahan, who developed it as a means to efficiently compute singular values.

The core idea is a two-sided process that builds orthonormal bases for the column and row spaces of A. Beginning with a unit vector v1, the algorithm iteratively computes:

- α_k = ||A v_k|| and u_k = A v_k / α_k,

- s = A^T u_k, then subtracts the component along the previous right vector to form s' = s − β_{k−1} v_{k−1} (with β_0 = 0),

- β_k = ||s'|| and v_{k+1} = s' / β_k.

In this notation, A v_k = α_k u_k and A^T u_k = α_k v_k + β_k v_{k−1}. After k steps, one obtains A V_k = U_k B_k and A^T U_k = V_k B_k^T, where B_k is bidiagonal. When k equals min(m, n), this yields the full factorization A = U B V^T with B bidiagonal.

Applications and significance: Golub–Kahan bidiagonalization is the standard foundation for computing the singular value decomposition of large matrices. After reducing A to bidiagonal form, the (often stable) QR algorithm is applied to B to extract singular values (and vectors). The method is central to large-scale SVD computations, as well as iterative solvers such as LSQR and LSMR, which exploit the two-sided process to solve linear least squares problems efficiently. In finite precision, orthogonality can degrade, and reorthogonalization may be used to maintain numerical stability.