Reorthogonalizing

Reorthogonalizing, or reorthogonalization, is the process of restoring orthogonality among a set of vectors that has degraded due to finite-precision arithmetic. In numerical linear algebra, many algorithms rely on an orthonormal basis of a Krylov subspace; rounding errors can cause loss of orthogonality, which in turn can lead to stagnation, duplication of eigenvalues, or inaccurate results. Reorthogonalization is applied during or after the generation of new vectors to recover the desired orthogonality.

Common approaches include full reorthogonalization, where each new vector is orthogonalized against all previously computed vectors, often using Gram-Schmidt or Householder transforms, sometimes with repeated passes until orthogonality criteria are met. Full reorthogonalization can be robust but increases computational cost. Partial or selective reorthogonalization scales down cost by reorthogonalizing only when the measured loss of orthogonality exceeds a threshold, or only for a subset of vectors. Partial reorthogonalization, such as Parlett’s method, estimates the growth of orthogonality errors and schedules reorthogonalization accordingly, offering a balance between accuracy and efficiency in large-scale problems.

Usage of reorthogonalization is essential in Krylov subspace methods like Lanczos and Arnoldi when solving for eigenvalues or linear systems, and is commonly implemented in sparse solvers and in ARPACK-type libraries. The choice of strategy depends on problem size, conditioning, and acceptable cost. Without reorthogonalization, numerical round-off can degrade the orthonormality of the basis, leading to degraded convergence or erroneous results.