Smoothed analysis of componentwise condition numbers for sparse matrices
Dennis Cheung, Felipe Cucker · IMA Journal of Numerical Analysis · 2014
We perform a smoothed analysis of the componentwise condition numbers for determinant computation, matrix inversion and linear equations solving for sparse n × n matrices. The bounds we obtain for the expectations of the logarithm of these condition numbers are, in all three cases, of the order 𝒪(log n). As a consequence, small bounds on the smoothed loss of accuracy for triangular linear systems follow.