We consider the iterative solution of large sparse linear least squares (LS) problems. Specifically, we focus on the design and implementation of reliable stopping criteria for the widely-used algorithm LSQR of Paige and Saunders. First we perform a backward perturbation analysis of the LS problem. We show why certain projections of the residual vector are good measures of convergence, and we propose stopping criteria that use these quantities. These projections are too expensive to compute to be used directly in practice. We show how to estimate them efficiently at every iteration of the algorithm LSQR. Our proposed stopping criteria can therefore be used in practice.
This talk is based on joint work with Xiao-Wen Chang, Chris Paige, Pavel Jiranek, and Serge Gratton.