Computation of Optimal Backward Perturbation Bounds for Large Sparse Linear Least Squares Problems

In this note we propose an algorithm based on the Lanczos bidiagonalization to approximate the backward perturbation bound for the large sparse linear squares problem. The algorithm requires ((m + n)l) operations where m and n are the size of the matrix under consideration and l <#60;<#60; min(m,n). The import of the proposed algorithm is illustrated by some examples coming from the Harwell-Boeing collection of test matrices.This revised version was published online in October 2005 with corrections to the Cover Date.