Sarah, S.W. Gaaf
Probabilistic bounds for the matrix condition number with extended Lanczos bidiagonalization

TU/e
MF5 097A
P O 513
5600 MB Eindhoven
The Netherlands
S.W.Gaaf@tue.nl
M.E. Hochstenbach

Reliable estimates for the condition number of a large (sparse) matrix $A$ are important in many applications. To get an upper bound for the condition number $\kappa(A)$ , a lower bound for the smallest singular value is needed. Krylov subspaces are usually unsuitable for finding a good approximation to the smallest singular value. Therefore, we study extended Krylov subspaces which turn out to be ideal for the simultaneous approximation of both the smallest and largest singular value of a matrix. First, we develop a new extended Lanczos bidiagonalization method. With this method we obtain a guaranteed lower bound for the condition number. Moreover, the method also yields a probabilistic upper bound for $\kappa(A)$ . This probabilistic upper bound holds with a user-chosen probability.