On Two-Stage Householder Orthogonalization
This work addresses stability issues in orthogonalization for numerical algorithms like Krylov subspace methods, offering an incremental improvement over existing methods.
The paper tackles the problem of orthogonalizing a matrix against another with orthonormal columns in numerical algorithms, proposing a two-stage Householder orthogonalization algorithm that is unconditionally stable, as shown by theoretical analysis and numerical experiments.
Two-stage orthogonalization is essential in numerical algorithms such as Krylov subspace methods. For this task we need to orthogonalize a matrix $A$ against another matrix $V$ with orthonormal columns. A common approach is to employ the block Gram--Schmidt algorithm. However, its stability largely depends on the condition number of $[V,A]$. While performing a Householder orthogonalization on $[V,A]$ is unconditionally stable, it does not utilize the knowledge that $V$ has orthonormal columns. To address these issues, we propose a two-stage Householder orthogonalization algorithm based on the generalized Householder transformation. Instead of explicitly orthogonalizing the entire $V$, our algorithm only needs to orthogonalizes a square submatrix of $V$. Theoretical analysis and numerical experiments demonstrate that our method is also unconditionally stable.