Generalized Golub--Kahan Bidiagonalization and Stopping Criteria

Abstract

The Golub--Kahan bidiagonalization algorithm has been widely used in solving least-squares problems and in the computation of the SVD of rectangular matrices. Here we propose an algorithm based on the Golub--Kahan process for the solution of augmented systems that minimizes the norm of the error and, in particular, we propose a novel estimator of the error similar to the one proposed by Hestenes and Stiefel for the conjugate gradient method and later developed by Golub, Meurant, and Strakoš. This estimator gives a lower bound for the error, and can be used as a stopping criterion for the whole process. We also propose an upper bound of the error based on Gauss--Radau quadrature. Finally, we show how we can transform augmented systems arising from the mixed finite-element approximation of partial differential equations in order to achieve a convergence rate independent of the finite dimensional problem size.