Premium
Spectral condition‐number estimation of large sparse matrices
Author(s) -
Avron Haim,
Druinsky Alex,
Toledo Sivan
Publication year - 2019
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2235
Subject(s) - mathematics , krylov subspace , singular value decomposition , singular value , condition number , rank (graph theory) , matrix (chemical analysis) , subspace topology , linear least squares , generalized minimal residual method , algorithm , qr decomposition , least squares function approximation , mathematical optimization , eigenvalues and eigenvectors , mathematical analysis , iterative method , statistics , combinatorics , physics , materials science , quantum mechanics , estimator , composite material
Summary We describe a randomized Krylov‐subspace method for estimating the spectral condition number of a real matrix A or indicating that it is numerically rank deficient. The main difficulty in estimating the condition number is the estimation of the smallest singular valueσ minof A . Our method estimates this value by solving a consistent linear least squares problem with a known solution using a specific Krylov‐subspace method called LSQR. In this method, the forward error tends to concentrate in the direction of a right singular vector corresponding toσ min . Extensive experiments show that the method is able to estimate well the condition number of a wide array of matrices. It can sometimes estimate the condition number when running dense singular value decomposition 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.