Reliable Iterative Condition-Number Estimation: Scientific Computing and Matrix Computations Seminar

Seminar: Departmental | February 20 | 12:10-1 p.m. | 380 Soda Hall

Speaker: Sivan Toledo, UC Berkeley

Sponsor: Electrical Engineering and Computer Sciences (EECS)

The talk will present a reliable Krylov-subspace method for estimating the spectral condition number of a matrix A. The main difficulty in estimating the condition number is the estimation of the smallest singular value \sigma_{\min} of A. Our method estimates this value by solving a consistent least-squares minimization problem with a known minimizer using a specific Krylov-subspace method called LSQR. In this method, the forward error tends to concentrate in the direction of a singular vector corresponding to \sigma_{\min}. Extensive experiments show that the method is very reliable. It is often much faster than a dense SVD and it can sometimes estimate the condition number when running a dense SVD would be impractical due to the computational cost or the memory requirements. The method uses very little memory (it inherits this property from LSQR) and it works equally well on square and rectangular matrices.

Event Contact: odedsc@cs.berkeley.edu, 510-516-4321