Smoothed analysis of componentwise condition numbers for sparse matrices

摘要

We perform a smoothed analysis of the component wise condition numbers for determinant computation, matrix inversion and linear equations solving for sparse n x n matrices. The bounds we obtain for the expectations of the logarithm of these condition numbers are, in all three cases, of the order O(log n). As a consequence, small bounds on the smoothed loss of accuracy for triangular linear systems follow.